1223. Chernobyl’ Eagle on a Roof(dp)&&poj3783

经典DP

n个鹰蛋 m层楼刚开始是二分想法　不过当数小于二分的那个值　貌似没发判断

dp[i][j] = min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k]) 选择第k层扔若碎了就用剩下ｉ-1个鹰蛋来测ｋ-1层若没碎就用ｉ个鹰蛋来测上面剩下的ｊ－ｋ层　

这样是三重循环　１０００＾３势必ＴＬＥ　不过以二分的思想来算　１０００层最多只需要１０个鹰蛋就可以测出来了　所以当ｎ大于１０的时候按１０来算就ＯＫ了　

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define INF 1e9

 int dp[][];

 void init()

 {

     int i,j,k;

     for(i = ; i <=  ; i++)

     {

         dp[][i] = i;

         //dp[0][i] = 0;

     }

     for(i = ;  i <=  ; i++)

     {

         dp[i][] = ;

         dp[i][] = ;

     }

     for(i = ; i <=  ; i++)

     {

         for(j = ; j <=  ; j++)

         {

             dp[i][j] = INF;

             for(k = ; k <= j ; k++)

             dp[i][j] = min(dp[i][j],max(dp[i-][k-],dp[i][j-k])+);

         }

     }

 }

 int main()

 {

     int n,m,i,j;

     init();

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(!n&&!m)

         break;

         if(n>)

         n = ;

         printf("%d\n",dp[n][m]);

     }

     return ;

 }

巴特西

1223. Chernobyl’ Eagle on a Roof(dp)&&poj3783

最新文章

热门文章