UVa 10934 DP Dropping water balloons

首先想一下特殊情况，如果只有一个气球，我们要确定高度只能从下往上一层一层地测试，因为如果气球一旦爆了，便无法测出气球的硬度。

如果气球有无数个，那么就可以用二分的方法来确定。

一般地，用d(i, j)表示用i个气球实验j次所能确定的楼层的最大高度。

我们假设第一个气球从第k层扔下，

如果气球爆了，那么剩下的i-1个气球实验j-1次，要能在下面的k-1层确定气球的硬度。所以这个k最大取d(i-1, j-1)+1
气球没爆，那么第1~k层就完全不用管了，i个气球剩下的j-1次测试就直接往上测试就行，最多能测试d(i, j-1)层

所以d(i, j) = d(i-1, j-1) + 1 + d(i, j-1)

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef unsigned long long LL;

 const int maxn =  + ;

 const int maxm = ;

 LL a[maxn][maxm];

 int n;

 LL h;

 int main()

 {

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

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

             a[i][j] = a[i-][j-] +  + a[i][j-];

     while(cin >> n >> h && n)

     {

         int i;

         for(i = ; i < maxm; i++) if(a[n][i] >= h) break;

         if(i < maxm) printf("%d\n", i);

         else puts("More than 63 trials needed.");

     }

     return ;

 }

代码君

巴特西

UVa 10934 DP Dropping water balloons

最新文章

热门文章