UVA10934 Dropping water balloons 题解

题意：

这是新生周，今年你的朋友们决定通过向新的计算机科学学生扔水球来进行入门仪式。他们已经装满了一大箱相同的水球，准备好参加活动。但命运会有意想不到的安排，水球竟然非常坚固，可以从几层楼高的地方掉下来而不破裂！

因此，你的朋友们找到了你求助。他们计划从校园里的一座高楼上扔水球，但希望尽可能少地花费力气将水球拿上楼梯，因此他们想知道从哪一层楼最低的楼层可以扔水球以确保它们会破裂。

你知道这栋建筑有 \(n\) 层楼，你的朋友们给了你 \(k\) 个相同的水球，你可以在试验中使用（和破坏）。

由于你也很懒，你想确定你必须进行的最少试验次数，以确切地确定可以从哪一层楼扔水球以确保它会破裂（或者在最坏的情况下，即使从顶层扔下，水球也不会破裂）。

一个试验包括从某一层楼扔下一个水球。如果一个水球在试验中没有破裂，你可以取回它，并再次用于另一个试验。

输入：多组数据，每次给定 \(k,n\) 。

输出：答案，超过 \(63\) 次则输出 More than 63 trials needed.

数据范围：\(1 \le k \le 100\) ，\(1 \le n \le 2^{63}-1\)

这个题第一想法肯定是二分，但是因为个数有限，并且我们也无法确定以怎样固定的策略达到最优

于是考虑dp，设 \(f(i,j)\) 表示有 \(i\) 个球扔 \(j\) 次能确定的最高位置。

考虑如何转移。设第 \(i\) 个球测试了第 \(x\) 层：

如果球爆了，则接下来的 \(f(i-1,j-1)\) 至多可以确定 \(x-1\) 层，即 \[ x = f(i-1,j-1) + 1 \]
如果球没爆，那就直接从 \(f(i,j-1)\) 转移，即 \[ f(i,j) = x + f(i,j-1) \]

诶，然后我们发现这个 \(x\) 可以直接去掉，变成 \[ f(i,j) = f(i-1,j-1) + 1 + f(i,j-1) \] 说实话我还第一次做到这样推转移方程的题，还挺巧妙的。

时间复杂度 \(\mathcal{O}(63n+q)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(222))

int f[N][N];
void init()
{
    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];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k; init();
    while(cin >> k >> n && k)
    {
        bool ok = false;
        for(int i = 1; i <= 63; i++)
            if(f[k][i] >= n) {
                ok = true; cout << i << '\n'; break;
            }
        if(!ok) cout << "More than 63 trials needed.\n";
    }
    return 0;
}