【题目大意】猜数字的游戏，可以猜N次，且只能猜大L次，求在一定的策略下，能猜到的最大的数。

----------------------------------------------------------
【分析】：很诡异的动态规划，看别人的分析：

1.先考虑L=0的情况，由于一次都不能猜错，因此只能从1开始，逐个向上猜，总数不能超过G；
    2.若G<=L，等价于G=L的情况，因为此时允许猜的次数限制了最大的数，总数为2^G
    3.一般的情况，比如L=1时，可以设想，只能猜错一次的话，这个数不能太大，否则猜错了一点作用也没有，因此要确保即使本次猜错也能在以后的G-1次猜中，这就转化成了(G-1,0)的情况，也就是说必胜的策略应当为先猜G，如果错，则从1~G-1逐次的猜，如果猜对了就转化成了(G-1,1)的情况，他应当再猜G+G-1……对于G=i,L=j的情况也是一样的考虑，可以列出状态转移方程：
opt[i][0]= i;
opt[i][i]= 2^i-1;
opt[i][j]= opt[i-1][j]+ opt[i-1][j-1]+ 1;

Source Code

• Source Code

  #include<cstdio>
  #include<string.h>
  #include<math.h>
  int main()
  {
  	int G,L,i,j,T,dp[31][31];
  	T=1;
  	while(scanf("%d %d",&G,&L) && G)
  	{
  		memset(dp,0,sizeof dp);
  		dp[0][0]=1;
  		for(i=1;i<=G;i++)
  		{
  			dp[i][0]=i;
  			for(j=1;j<=L;j++)
  				if(j>=i)
  					dp[i][j]=pow(2.0,i)-1;
  				else
  					dp[i][j]=dp[i-1][j]+1+dp[i-1][j-1];
  		}
  		printf("Case %d: %d\n",T++,dp[G][L]);
  	}
  	return 0;
  }