uva 10934 裝滿水的氣球

題意和思路見:

http://blog.csdn.net/shuangde800/article/details/11273123

我的想法：

首先問題轉化一下

将問題轉化成：定義f[i][j] 表示給i個水球和j次實驗機會，最高能夠測試到幾層~

則會有如下的轉移方程：

f[i][j] = f[i][j-1] + f[i-1][j-1] + 1;

後一部分是說選在第k層試第一次，如果摔破了，說明邊界在下面的層中。

是以說選的那個k層，k最大應該滿足k <= f[i-1][j-1] + 1; 因為要保證一旦水球在第k層摔壞了，下面的所有層都可以在還有i-1個球和j-1次機會時測出來；

前一部分表示選在k層試第一次，但是球并沒有摔壞。這個時候最高就是在k層的基礎上，加上 還有i個球和j-1次機會時能夠再往上測幾層~即f[i][j-1];

是以綜上兩部分，f[i][j]最大就等于f[i-1][j-1] + 1 + f[i][j-1];

code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

long long f[110][65];

void init(){
      memset(f, 0, sizeof(f));
      for(int i = 1;  i < 64; i++){
            for(int j = 1; j < 64; j++){
                  f[i][j] = f[i][j-1] + 1 + f[i-1][j-1];
            }
      }
}
int main(){
      init();
      int k;
      long long n;
      while(scanf("%d%lld",&k,&n) != EOF){
            if(k == 0) break;
            k = min(k, 63);
            bool ok = false;
            for(int i = 0; i <= 63; i++ ){
                  if(f[k][i] >= n){
                        printf("%d\n",i);
                        ok = true;
                        break;
                  }
            }
            if(!ok) printf("More than 63 trials needed.\n");
      }
      return 0;
}