青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

【題目大意】猜數(shù)字的游戲，可以猜N次，且只能猜大L次，求在一定的策略下，能猜到的最大的數(shù)。

----------------------------------------------------------
【分析】：很詭異的動態(tài)規(guī)劃，看別人的分析：

1.先考慮L=0的情況，由于一次都不能猜錯，因此只能從1開始，逐個向上猜，總數(shù)不能超過G；
    2.若G<=L，等價于G=L的情況，因為此時允許猜的次數(shù)限制了最大的數(shù)，總數(shù)為2^G
    3.一般的情況，比如L=1時，可以設(shè)想，只能猜錯一次的話，這個數(shù)不能太大，否則猜錯了一點作用也沒有，因此要確保即使本次猜錯也能在以后的G-1次猜中，這就轉(zhuǎn)化成了(G-1,0)的情況，也就是說必勝的策略應(yīng)當為先猜G，如果錯，則從1~G-1逐次的猜，如果猜對了就轉(zhuǎn)化成了(G-1,1)的情況，他應(yīng)當再猜G+G-1……對于G=i,L=j的情況也是一樣的考慮，可以列出狀態(tài)轉(zhuǎn)移方程：
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;
  }