UVa 10934 Dropping water balloons

题目

◇题目传送门◆（由于UVa较慢，这里提供一份vjudge的链接）
◇题目传送门（vjudge）◆

题目大意

有$K$个一模一样的水球，在一个有$N$层楼高的高楼进行测试。但是你很懒，所以你想使用最少的实验次数来知道一个水球的硬度到底是多少（若从某层楼扔下来刚好破，则水球的硬度为这层楼的标号），或得出结论：在最高层也摔不破。注意一个水球不会被实验所损坏（即若这个球没破，这个球的还是原来的硬度）。

求出最少需要的实验次数。注意若63次实验仍然不能得出结果，则输出：More than 63 trials needed.。

思路

二分？暴力？似乎有了$K$的限制，一切都变了。。。

我们换一下思路：给定水球个数及实验次数，求出最高实验楼层。这道题就转化为了DP。

定义状态$f[i][j]$为使用$i$个球，做$j$次实验所能测试的楼的最高层数。接下来考虑决策：

设当前测试楼层为$k$。

若水球在第$k$层破了，则说明之前的$k-1$层必须使用$i-1$个球实验$j-1$次测出。则当$k=f[i-1][j-1]+1$时，该决策最优。

若水球没有破，则我们可以将第$k+1$层看做第$1$层以后继续实验$f[i][j-1]$层楼。

综上所述，我们可列出状态转移方程：

实现细节

注意$f[i][j]$的值可能超过int，请使用long long。

为了保证在规定内时间出解，请使用打表法预处理出所有的$f[i][j]$。时间复杂度为$O(2^{16})$，能够过。

正解代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int K;
long long N;
long long f[65][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-1][j-1]+1+f[i][j-1];
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifInit();//直接打表，预处理f[i][j]while(scanf("%d %lld",&K,&N)!=EOF&&K&&N) {K=min(K,63);//K与63取min!!!//因为N<2^64，根据二分法，最多只需63个球就可以得到解bool ok=false;for(int i=0;i<64;i++)if(f[K][i]>=N) {printf("%d\n",i);ok=true;break;}//注意应枚举实验次数找到f[K][i]大于等于N的状态if(!ok)puts("More than 63 trials needed.");//没有找到，即63次实验也测不出}return 0;
}