UVa 10934 - Dropping Water balloons(DP)

给出 n 个相同的气球, k 层楼,问最少几次试验可以知道气球最高从多少层扔下不会爆。
用 d [ i ] [ j ] 表示用 i 个球,实验 j 次所能确定的最高楼层数,对于每一次试验分爆和不爆两种情况讨论:
1、爆了,转移到 d [ i − 1 ] [ j − 1 ] + 1 ,用掉了1个球和一次试验机会。
2、没爆,将当前测试层数的上一层当做第1层继续进行试验,转移到 d [ i ] [ j − 1 ] 。
得出转移方程 d [ i ] [ j ] = d [ i − 1 ] [ j − 1 ] + 1 + d
[ i ] [ j − 1 ] 。
好久之前做的题了,具体思路见紫书。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
ULL d[110][65],k,n;
int main(){
for(int i=1;i<110;++i)
for(int j=1;j<65;++j)
d[i][j]=d[i-1][j-1]+1+d[i][j-1];
while(~scanf("%llu%llu",&k,&n)&&k){
int ans = 0;
for(int i=64;i>=0;--i)
if(d[k][i]<n){
ans=i+1;
break;
}
if(ans<=63) printf("%d\n",ans);
else puts("More than 63 trials needed.");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。