题目链接：http://poj.org/problem?id=1243
题意：让你猜一个物品的价格，猜低了或者猜高了都会提示你。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]，那么为了最大化，必定要使x=dp[i-1][j-1]+1(若不选x刚好大于dp[i-1][j-1],太小会使范围重复，太大则不能在规则内猜得到)
如果猜对了，那么就赢了，即总范围+1
所以在（i，j）的情况下我们能猜的最大范围就是 dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j]；
例如：3 1先选择点3，假设目标低于3，还有两次机会必定能猜到。假设目标高于3，再选择5，假设目标低于5，还有一次机会刚好猜4，若高于5，刚好猜6.所以总范围为6.即dp[3][1]=dp[2][0]+1(点3本身)+dp[2][1].
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <vector> #include <set> #include <map> #define LL long long #define mod 1000000007 #define inf 0x3f3f3f3f #define N 50010 using namespace std; int dp[50][50]; void init() { for(int i=1;i<=30;i++) { dp[i][0]=i;dp[i][i]=(1<<i)-1; for(int j=1;j<i;j++) { dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1; } } } int main() { int n,m,cas=1; init(); while(scanf("%d%d",&n,&m)>0) { if(n+m==0)break; if(n<m)m=n; printf("Case %d: %d ",cas++,dp[n][m]); } }