UVA 10328 -—— Coin Toss【DP & 大数】

UVA 10328 -—— Coin Toss【DP & 大数】

​​题目传送门​​

题意：

给你一个硬币，抛掷n次，问出现连续至少k个正面向上（H）的情况有多少种。

分析：

原题中问出现连续至少k个H的情况，很难下手。我们可以试着将问题转化一下，设 dp[i][j] 表示抛掷i个硬币出现连续至多 j 个H 的情况种数。

实际出现连续至少k个H，即出现连续k个H，k+1个H，…n个H的并集，等价于dp[n][n]-dp[n][k-1]，即从连续至多n个H的情况（所有抛掷情况种类数）减去连续至多（k-1）个H的情况，这保证得到的所有情况一定至少有k个连续的H。

现在问题就变成了怎么求dp[i][j]。

i <= j：dp[i][j] = dp[i-1][j] × 2，即从上一阶段得到的抛掷序列后面增加正和反两种情况，如果出现连续的H个数大于j个，这种情况是非法的，但很显然此时不会出现这种情况。当前位置随便放。

i > j： 如果继续用 dp[i][j] = dp[i-1][j] × 2 就不行了。因为如果 从第 i - j 个到第 i - 1 全是H ，那么这时候在第i个位置再加一个H，就会出现连续的H个数大于j个的非法状态，所以我们需要减掉 从 i - j 到第 i - 1 全是H 的这种情况。那么这种情况有多少种呢？我们考虑该状态是如何转移而来的。试想第 i - j - 1 个位置应该是什么呢？很明显只能是T。如果是H那就会出现非法状态了。那在第 i - j - 1 之前的位置呢。无论H和T都可以，只要不出现连续的H个数大于j的非法状态即可，这就是 dp[i-j-2][j]。

那么这样，dp[i][j] = dp[i-1][j] × 2 - dp[i-j-2][j]。

但这还是不够的。我们之前的推导都是基于第i-j-1个位置一定存在的前提下（i>j不能保证第i-j-1个位置一定存在），那如果第i-j-1个位置不存在，第i-j-2个位置也就不存在，上述方程也就不成立了。但这种情况很好想，此时一定是i==j+1，从第1个位置到第j个位置全部都是H，只有这一种情况，所以方程变成 dp[i][j]=dp[i-1][j] × 2 - 1。

综上，状态转移方程为：i<=j：dp[i][j] = dp[i-1][j] × 2; i==j+1：dp[i][j] = dp[i-1][j] × 2 - 1; i>j+1：dp[i][j] = dp[i-1][j] × 2 - dp[i-j-2][j]

ans=dp[n][n] - dp[n][k-1]

AC代码：

import java.math.BigInteger;import java.util.Scanner;public class Main { public static void main(String[] args) { BigInteger a, b; BigInteger dp[][] = new BigInteger[105][105]; //初始化 for (int i = 0; i <= 100; i++) { dp[0][i] = BigInteger.valueOf(1); dp[i][0] = BigInteger.valueOf(1); dp[1][i] = BigInteger.valueOf(2); } for (int i = 1; i <= 100; i++) { for (int j = 1; j <= 100; j++) { if (i <= j) dp[i][j] = dp[i - 1][j].multiply(BigInteger.valueOf(2)); else if (i == j + 1) dp[i][j] = dp[i - 1][j].multiply(BigInteger.valueOf(2)).subtract(BigInteger.valueOf(1)); else dp[i][j] = dp[i - 1][j].multiply(BigInteger.valueOf(2)).subtract(dp[i - j - 2][j]); } } Scanner in = new Scanner(System.in); while (in.hasNext()) { a = BigInteger.valueOf(in.nextInt()); b = BigInteger.valueOf(in.nextInt()).subtract(BigInteger.valueOf(1)); System.out.println(dp[a.intValue()][a.intValue()].subtract(dp[a.intValue()][b.intValue()])); } in.close(); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。