题意:
猜数字, 给定 G, L, G 表示可以猜的次数, 每猜一次, G减一, 假如猜的 number 大于 target, L 还需减一, 当 L == -1 或者 G==0 时, 若还没猜中, 则失败
思路:
1. 举例子
<1> 当 G = 3, L = 0 时, 只能从 1 向上猜, 最大的数字是 3
<2> 当 G = 2, L = 1 时, 不必从 1 猜起, 假设猜 k, 假如小了, 状态变成 <G,L>(1,0), 由 (1) 得到的规律知, k 不能大于 2; 假如大了, 那么状态变成 <G,L>(1,1), 还有一次机会, 可见, <G,L>(2,1) 等于 3
<3> 当 <G,L>(3,1) 时, 仍然假设猜 K, 假如小了, 状态变成 <G,L>(2,0), 假如大了, 变成<G,L>(2,1), 又 <G,L>(2,1)可以保证3个数能被猜出, 所以 <3,1> 等于 6
2. 从 1 的例子足以看出规律, 一个状态<G,L> 能够保证多少个数能被猜出, 比如 <G,L>(3,1)=6, <G,L>(3,0)=3, <G,L>(2,1)=3
3. 状态转移方程, dp[i][j] 表示G=i, L = j 在最差的情况下能够保证被猜出数的个数
dp[i][j] = dp[i-1][j-1] (low 了) + 1 + dp[i-1][j](high)了
4. 如果 j >= i, 那么 dp[i][j] = dp[i][i-1]
总结:
1. 第 11 行代码, j 应该从 1 开始, WA 过一次
代码:
#includeusing namespace std;int G, L;int dp[100][100];int solve_dp() { for(int i = 0; i <= G; i++) dp[i][0] = i; for(int i = 1; i <= G; i ++) { for(int j = 1; j <= L; j++) { if(j >= i) dp[i][j] = dp[i][i-1]; else dp[i][j] = dp[i-1][j-1]+1+dp[i-1][j]; } } return dp[G][L];}int main() { freopen("E:\\Copy\\ACM\\测试用例\\in.txt", "r", stdin); int testcase = 0; while(scanf("%d%d", &G, &L) && G != 0) { testcase++; printf("Case %d: %d\n", testcase, solve_dp()); } return 0;}