【UVa】10328 - Coin Toss（递推 & 对立事件 & java）

点击打开题目

Toss is an important part of any event. When everything becomes equal toss is the ultimate decider. Normally a fair coin is used for Toss. A coin has two sides head(H) and tail(T). Superstition may work in case of choosing head or tail. If anyone becomes winner choosing head he always wants to choose head. Nobody believes that his winning chance is 50-50. However in this problem we will deal with a fair coin and n times tossing of such a coin. The result of such a tossing can be represented by a string. Such as if 3 times tossing is used then there are possible 8 outcomes. HHH HHT HTH HTT THH THT TTH TTT

As the coin is fair we can consider that the probability of each outcome is also equal. For simplicity we can consider that if the same thing is repeated 8 times we can expect to get each possible sequence once.

In the above example we see 1 sequence has 3 consecutive H, 3 sequence has 2 consecutive H and 7 sequence has at least single H. You have to generalize it. Suppose a coin is tossed n times. And the same process is repeated 2n times. How many sequence you will get which contains a sequence of H of length at least k.

Input The input will start with two positive integer, n and k (1 ≤ k ≤ n ≤ 100). Input is terminated by EOF.

Output For each test case show the result in a line as specified in the problem statement.

Sample Input 4 1 4 2 4 3 4 4 6 2

Sample Output 15 8 3 1 43

递推的问题。

我们直接求很麻烦，这道题还是得用对立事件求。

数组dp[ i ][ j ]，表示，一共i个硬币，不超过j个满足条件（为H）。

有i个硬币时，如果i < j+1，那么它对于i-1的情况来说，最后一个硬币的位置就可以随便放了。

如果i > j + 1，dp[ i ] [ j ] = dp [ i - 1 ] [ j ] * 2 - x（不满足条件的部分）

然后我们来考虑这个x怎么求，既然是不满足条件，那么肯定是第i的位置放了H，前面的都是H，从而这些连续的H大于j。那么就考虑dp[ i - 1 - j - 1 ]（中间这 j - 1 个全为H，加上第i个H，就不满足条件了），所以：

dp [ i ] [ j ] = dp [ i - 1 ] [ j ] * 2 - dp [ i - j - 2 ] [ j ]

那么我们就差最后一个了：i == j + 1的情况了。（因为 i - j - 2 就等于 -1 了，用递推公式会RE的）

这种情况只有一种，即是全是H。

那么它就为：dp [ i ] [ j ] = dp [ i - 1 ] [ j ] * 2 - 1

有了递推公式，用BigDecimal写就好写多了，毕竟数据也不大。（本来还想着用矩阵快速幂写呢，发现根本没有取模）

代码如下：

import java.math.BigDecimal;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
	    BigDecimal dp[][] = new BigDecimal [105][105];
	    for (int i = 0 ; i <= 100 ; i++)
	    {
	        dp[0][i] = new BigDecimal(1);
	        dp[i][0] = new BigDecimal(1);
	        dp[1][i] = new BigDecimal(2);
	    }
	    dp[1][0] = new BigDecimal(1);
	    for (int i = 2 ; i <= 100 ; i++)
	    {
	        for (int j = 1 ; j <= 100 ; j++)		//j为0，
	        {
	            dp[i][j] = dp[i-1][j].multiply(BigDecimal.valueOf(2));
	            if (i == j+1)
	                dp[i][j] = dp[i][j].add(BigDecimal.valueOf(-1));
	            else if (i > j+1)
	                dp[i][j] = dp[i][j].add(dp[i-1-j-1][j].negate());
	        }
	    }
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext())
		{
		    int n = sc.nextInt();
		    int k = sc.nextInt();
		    System.out.println(dp[n][n].add(dp[n][k-1].negate()));
		}
	}
}