题解 UVA10934 【装满水的气球 Dropping water balloons】

rayluo · 2020-02-19 22:45:27 · 题解

Update 2020-3-23

• 再次核对英文版本后发现结束条件仅为 k=0，对 n 无限制。

description :

• 多组输入，最后一组 k=0 且不需要处理。

• 每组输入 n，k。n 为楼的最高层数，k 为你有多少个水球。

• 从一定高度的楼层（小于等于 n )把水球扔下去，若大于水球的承受限度就破了，并且你就少了一个水球。小于等于则没破，这个水球可继续使用。

• k 个水球的承受限度是相同的。

问你最少多少次可以将水球的承受限度测出来，如果次数多于63次则输出 "More than 63 trials needed."。

solution :

如果不考虑水球的个数有上限的话，就是一个基本的二分。假如我们现在仍用二分的话，可能会导致无球可用的情况，但 n 是一个64位整型，也就是要开 unsigned long long，逐个枚举肯定是不现实的。于是我们试一试从正面设 dp 方程。

我们令 f(i,j) 为最坏情况下，我们通过使用 i 个水球，进行 j 次实验所能确定的承受限度。

假设我们这第 i 个水球试的是第 x 层。如果这个水球破了，则承受限度小于 x，我们耗费了一个水球和一次实验，那么我们接下来的 f(i-1,j-1) 最多可以确认 (x-1) 层，即 x=f(i-1,j-1)+1。如果这个水球没破，则承受限度大于等于 x ，耗费了一次实验，我们接下来就从第 x 层开始，往后测试 f(i,j-1) 层。

所以转移方程为 f(i,j)=x+f(i,j-1)，也就是 f(i,j)=f(i-1,j-1)+1+f(i,j-1)。

根据题目要求，我们最多有100个水球，进行63次实验，可以先一遍预处理，询问时再枚举实验的次数，最大为63，看什么时候大于等于 n。若一直不符合要求，最后输出 "More than 63 trials needed."。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define ll unsigned long long
const int N=110;
in ll read()
{
    ll w=0,r=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')r=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*r;
}
ll k,n;
ll f[N][N];  //第i个球，第j次实验可以确定的硬度 

void pre()  //预处理所有可能性 
{
    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];  //转移，已解释过 
        }
    } 
}

int main()
{
    k=read();
    n=read();
    pre();
    while(k!=0)
    {
        bool flag=0;  //判断是否找到符合条件的答案 
        for(int i=1;i<=63;i++)  //枚举试验次数 
        {
            if(f[k][i]>=n)  //符合要求 
            {
                cout<<i<<endl;
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            puts("More than 63 trials needed.");
        }
        k=read();
        n=read();
    }
    return 0;
} 

如有错误或问题，请指出。