动态规划
题意：让你猜一个物品的价格，猜低了或者猜高了都会提示你。G,L，表示你有G次机会猜一个数，如果猜错了，G会减少1次，如果你的错误是应该是猜高了，那么L也会少一次（猜低了L不会少）。如果G次机会都用完了，则输；若G次机会还有剩余，而L次机会用完了，这时再猜一个数，若猜高了，那么也输了。让你确定一个数字N，以保证在G,L的条件下，你一定能猜到[1,N]以内的任何一个数
1.如果L等于0，也就是说你在猜的过程中，绝对不能猜高，所以你只能从1开始猜，并依次为2,3,4……最大能猜到的数是G，所以N=G,这样才能保证你一定能猜到其中的任何一个数
2.L>G，这是个迷惑的情况，其实L比G大是没意义的，因为无论猜高了猜低了G都会减少，所以G一定先为0，G L等价于G G
3.L=G，这个情况和上面的情况是一样的，这样的猜测是不需要考虑什么猜高猜低的，因为G也一定是先变为0，那么像G G这种情况能猜的范围是多少呢？就是N=(2^G)-1，这是由二分查找的性质可以得知的
4.L<G，这个才是真正需要DP的。这样考虑策略，dp[i][j]表示还有i次机会，j次猜高的机会情况下能猜测的最大长度（即N）
我们猜测一个数字x
如果猜低，剩下i-1次机会，j次猜高的机会，那么正确的数字在[x+1, INF)范围内，假设我们已经知道了dp[i-1][j]，那么这个数字只能出现在[x+1 , dp[i-1][j]+x]范围内，才能保证我们一定猜到它
如果猜高，剩下i-1次机会，j-1次猜高的机会，那么正确的数字在[1,x-1]范围内，假设我们已经知道了dp[i-1][j-1]，那么为了最大化，必定有dp[i-1][j-1]=x-1
如果猜对了，那么就赢了
所以在（i，j）的情况下我们能猜的最大范围就是 dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j]；
我们可以先dp，输入后直接打表即可
/* 初始化：dp[i][0]=i; dp[i][i]=(1<<i)-1; 状态转移方程：dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j]; */ #include <cstdio> #include <cstring> #define N 30 int dp[N+10][N+10],g,l; int main() { for(int i=0; i<=N; i++) { dp[i][0]=i; dp[i][i]=(1<<i)-1; } for(int i=1; i<=N; i++) for(int j=1; j<i; j++) dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j]; int Case=0; while(scanf("%d%d",&g,&l) && (g||l)) { printf("Case %d: ",++Case); if(l>g) printf("%d\n",dp[g][g]); else printf("%d\n",dp[g][l]); } return 0; }