题目描述

你的任务是借助一个n层的高楼确定气球的硬度（所有气球硬度相同）。实验过程是这样的：每次你拿着一个气球爬到第f层楼，将它摔到地面。如果气球破了，说明它的硬度不超过$f$；如果没破，说明硬度至少为$f$。注意，气球不会被实验所“磨损”。换句话说，如果在某层楼上往下摔，气球没破，那么在同一层楼不管再摔多少次它也不会破。

给你k个气球用来实验（可以打破它们）。你的任务是求出至少需要多少次实验，才能确定气球的硬度（或者得出结论：站在最高层也摔不破）。输入每行包含两个整数$k , n（1≤k≤100，1≤n<2^{64}）$，输出最少需要的实验次数。如果 $63$ 次不够，输出“More than 63 trials needed”。

对题目的思考与收获：
1. 首先想到的是用f[i][j]表示i个气球，j层楼的最小实验次数，但是注意到题目给到的范围$1≤n<2^{64}$,这样的状态表示数组是开不出来的，即使可以开出来时间复杂度也太高了，因此我们需要考虑其它方法。
2. 用f[i][j]表示i个气球，j次实验所能测试的最高楼层数。即当我们有i个气球和j次实验机会时，我们可以测试出所有硬度为$[0,f[i][j]]$的气球的硬度。

这里我们需要考虑一个问题：我们的实验从哪一层开始才是最优的？
由于最优，因此我们需要在保证能测试出硬度的前提下选择尽量高的楼层。

假设气球在$k$层抛下破了，这时我们还剩下$i - 1$个气球和$j - 1$次实验机会，如果要保证实验一定可以测出硬度，那么$i - 1$个气球和$j - 1$次实验机会刚好测出$k - 1$层就是最优解，即f[i - 1][j - 1] = k - 1,k = f[i - 1][j - 1] + 1就是我们的最优起点楼层。如果破了我们也能保证测试出硬度，如果没破我们还可以继续增高可以测试的楼层。为了取到最优解，即选择到尽量高的楼层，我们肯定希望在k层气球是没有摔破的，在气球没破的情况下我们的气球还剩i个，实验次数还剩j - 1次，这样我们还可以增加的层数就是f[i][j - 1]。

综上我们可以得出状态转移方程:f[i][j] = f[i - 1][j - 1] + 1 + f[i][j - 1];

C++ Code

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;

const int N = 110;

ULL f[N][N];
int k;
ULL n;

int main()
{
    //freopen("out.txt","w",stdout);
    for(int i = 1; i <= 100; ++i){ // 打表
        for(int j = 1;  j<= 63; ++j){
            f[i][j] = f[i - 1][j - 1] + 1 + f[i][j - 1];
        }
    }
    while(scanf("%d%llu",&k,&n),k){
        if(f[k][63] < n)puts("More than 63 trials needed.");
        else for(int i = 1; i <= 63; ++i){
            if(f[k][i] >= n){ // 不一定是恰好，因此这里用的是大于等于而不是等于
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}