UVA10934 Dropping water balloons（经典题 dp状态比较难想）

逃离我推掉我的手 2021-12-14 20:29 161阅读 0赞

## 题意：k个水球，现在在一个n层建筑物上，水球可能在某一层层以上扔下去会破掉，现在求一个最少的次数使得用这k个水球能确定出哪一层。 ##

## 分析：假设你有无数个水球的情况下，那么最少的次数肯定就是用二分的方法：首先在正中间摔下去，如果破的话，说明目标位置在下半部分，不破的话说明是在上半部分。上后继续在对应的部分再二分下去……需要logn次。但是这题的水球数量有限，例如，只有一个水球的情况下，你直接在正中间楼层放下去，如果摔破的话，那么你就没有其它球继续做实验了。所以你只能从第一层开始一直往上丢，第一个摔破的楼层就是目标楼层了。那么最糟糕的情况下就是要做N次。这样的话还是不太好想，所以要把问题转换一下，变成：“给k个气球，丢j次，最多能确定第几层？”这样，就可以用f(i, j)状态来表示第i个气球，丢j次最多确定的层数。对于f(i, j), 我们不知道它最多可以确定第几层，假设第一次在x层仍球，如果球破了，那么我们花费了一个球和仍了一次的费用，   我们可以知道f(i-1, j-1)可以确定的层数，那么就可以确定x = f(i-1, j-1) + 1。如果在x层时如果球没有破，那么我们只花费了仍一次的费用，还剩下i个球，j-1次可以用，那么用这些可以确定的层数f(i, j-1)，所以，得到递推式，推出最高能确定的层数：f(i, j) = f(i-1, j-1) + 1 + f(i, j-1)。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxk = 100;
    const int maxa = 63;
    
    unsigned long long d[maxk+1][maxa+1];
    
    int main()
    {
        memset(d, 0, sizeof(d));
        for(int i = 1; i <= maxk; i++)
            for(int j = 1; j <= maxa; j++)
                d[i][j] = d[i-1][j-1] + 1 + d[i][j-1];
        int k;
        unsigned long long n;
        while(cin >> k >> n && k)
        {
            int ans = -1;
            for(int i = 1; i <= maxa; i++)
                if(d[k][i] >= n)
                {
                    ans = i;
                    break;
                }
            if(ans < 0) cout << "More than " << maxa << " trials needed.\n";
            else cout << ans << "\n";
        }
        return 0;
    }