本文共 1746 字，大约阅读时间需要 5 分钟。

首先，题目的意思是让你去扔气球，砸小孩，非常玄幻。

【要点】

为什么2的时候是14呢？

关键在于我们虚晃一枪，先扔了50，如果没爆，那赚了，只需要测50就可以了（转移到了50的状态，下面的50都没用了，是不是非常眼熟？）

即使爆了，我们还可以继续扔，继续诓？

但是，50爆了，我们只能从1开始1 2 3 4 。。 保不好要扔49次，因此我们要找一个最好的地方去扔，避免浪费，还有效。

啊，想到是dp， 不要正面去想啊，找一个切入点。

【切入点】

除了“在任何情况下停下都是最佳的”，还有一个，就是结点的状态啊不，就是初始值一定要搞对。。。  初始值，。。。按照一样的模式往前发展，就很好。。。我倒霉觉得状态转移方程多重要。。。。

楼房数量非常大，所以我们可以用数组存一下，每次几个球，能达到的数量固定，n这么大， 只要线性比较一下就好了。

emmmmm，，，。。。 n这么大

然后。。 然后。。然后你随便找个地方k，

这里数组存储的只能代表楼层了

然后爆了就是在下面，没就是在中间

思维很重要。【严肃脸】

转个弯儿。。。 不然怎么也想不到啊

限定了最多63次，代码我没再写了 ，饭正就是对于一种情况n，就有63次尝试，最后匹配一下。。

真是想不出。。。

但是【严肃脸】

【其实一共就三个量，一个那么大，就把那条路毒死了】

【就像下一篇gym里二分那个题，有1e9，验证一个一个往下走的思路是正确的，但是随随便几个数据就能让你超时】

【这时候就想一下反向的存储来help】

参考网站 ：

代码也是参考的那里的。。  我。。

/**===================================================== *   This is a solution for ACM/ICPC problem * *   @source      : uva-10934 Dropping water balloons *   @description : dp *   @author      : shuangde *   @blog        : blog.csdn.net/shuangde800 *   @email       : zengshuangde@gmail.com *   Copyright (C) 2013/09/09 12:49 All rights reserved.  *======================================================*/ #include 
   
    using namespace std; typedef long long int64;const int INF = 0x3f3f3f3f; int64 f[110][65]; inline void init() {    memset(f, 0, sizeof(f));    for (int i = 1; i < 64; ++i) {        for (int j = 1; j < 64; ++j) {             f[i][j] = f[i][j-1] + f[i-1][j-1] + 1;        }    }}int main(){     init();    int k;    int64 n;     while (~scanf("%d%lld", &k, &n) && k) {         k = min(63, k);        bool ok = false;        for (int i = 0; i <= 63; ++i) {            if (f[k][i] >= n) {                printf("%d\n", i);                 ok = true;                break;            }         }        if (!ok) puts("More than 63 trials needed.");    }     return 0;}