题意
有个N层的高楼和若干个棋子，所有的棋子都是一样的。棋子从楼的某层E扔到地上不会碎(0 <= E <= N)，但从比这个楼层高的地方扔到地上都会碎。给出楼的高度N，以及棋子的数量M，你来找出这个E(0 <= E <= N)，问最坏情况下需要实验多少次才能计算出准确的E（如果棋子摔碎了，就不能继续用这个棋子进行测试了）。
1 <= T <= 50000，1 <= N <= 10^18, 1 <= M <= 64。
分析
这题是04年的论文题，文中提到了很多种优化方法。
朴素的想法是设f[i,j]表示i层楼用j个棋子最坏情况下需要多少步，转移是f[i,j]=min(max(f[w-1,j-1],f[i-w,j])+1)。复杂度是\(O(n^3)\)。
注意到当没有蛋数量的限制时，答案就是二分查找的最坏情况，是\(log_2n\)。也就是说如果\(j>log_2n\)就直接输出就好了。复杂度变成了\(O(n^2log_2n)\)。
根据定义不难发现有\(f[i-1,j]<=f[i,j]\)，那么转移的时候决策点的贡献是一个单峰函数，可以三分，由于坐标均为整数，所以可以二分。复杂度变成了\(O(n(log_2n)^2)\)。
再推一下不难发现这个转移有决策单调性。复杂度变成了\(O(nlog_2n)\)。
这已经是优化到不能再优化了，然而还是不能通过本题，于是只能考虑另外的做法。
设f[i,j]表示有i个棋子扔了j次最坏情况下可以计算出多少楼。
转移时f[i,j]=f[i-1,j-1]+f[i,j-1]+1
为什么是这样呢？考虑第一次扔到某一个位置w，如果棋子坏了那么就取剩下的，就是f[i-1,j-1]；否则就可以继续往上算f[i,j-1]层。显然w取f[i-1,j-1]+1时是最优的，所以还要+1。
边界条件：f[n,1]=1,f[1,n]=n。根据归纳法不难得出f[2,n]=n*(n+1)/2。
注意到\(C_j^i<=f[i,j]\)，所以有用的状态其实并不多，可以全部预处理出来然后二分就好了。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=2000005;
const LL MX=1e18;
LL n;
int m;
vector<LL> f[65];
int main()
{
for (int i=0;i<=N;i++) f[0].push_back(0);
for (int i=1;i<=64;i++)
{
f[i].push_back(0);
for (int j=1;j<=N;j++)
{
f[i].push_back(f[i][j-1]+f[i-1][j-1]+1);
if (f[i][j]>MX) break;
}
}
int T;scanf("%d",&T);
while (T--)
{
scanf("%lld%d",&n,&m);
if (m==1) printf("%lld\n",n);
else if (m==2)
{
LL x=sqrt(n*2);
if (x*(x+1)<n*2) x++;
printf("%lld\n",x);
}
else
{
int x=lower_bound(f[m].begin(),f[m].end(),n)-f[m].begin();
printf("%d\n",x);
}
}
return 0;
}
转播
