ACM DP Dropping water balloons

蔚落 2022-06-11 09:36 62阅读 0赞

滴，集训第十七天打卡。

感觉这阵子都是dp啊...

**uva 10934**

## Dropping water balloons ##

**![20170804101501032][]**

**![20170804101506613][]**

**题目大意：你有k个一模一样的水球，在一个n层楼的建筑物上进行测试，你想知道水球最低从几层楼往下丢可以让水球破掉。由于你很懒，所以你想要丢最少次水球来测出水球刚好破掉的最低楼层。（在最糟情况下，水球在顶楼也不会破）你可以在某一层楼丢下水球来测试，如果水球没破，你可以再捡起来继续用。**

**思路：好不容易看懂了题目还是一头雾水...看了题解才懂了..这里要转换一下思路，把问题变成“给k个气球，丢j次，最多能确定第几层？”，这样就可以得到递推式：dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+dp\[i\]\[j-1\]+1**

#include<stdio.h>
    long long dp[105][105];
    int main()
    {
        int i,j,k,m,n,p,q;
        long long x,y,z;
        for(i=1;i<=100;i++)
          for(j=1;j<=63;j++)
            dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1;
        while(scanf("%d%lld",&n,&x)&&n)
        {
            for(i=1;i<=63;i++)
            {
            	if(dp[n][i]>=x)
    			{
    				printf("%d\n",i);
    				break;
    			}
            }      
            if(i>63) 
    		printf("More than 63 trials needed.\n");
        }
    }

[20170804101501032]: /images/20220611/060f4e3fb4e0480a8e36ddf92ed740d9.png
[20170804101506613]: /images/20220611/e91a68fbb6aa4a40bf23ac1e56adda93.png

发表评论取消回复

表情：

评论列表（有 0 条评论，62人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP专辑】ACM动态规划总结

动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建模抽象能力、灵活度。本人动态规划博客地址：[http://bl

迷南。/ 2022年08月21日 07:43/ 0 赞/ 150 阅读

相关 uva 10934—— Dropping water balloons

题意：给定K个气球，然后n层楼的高度，求确定气球的硬度（站在多高能摔破）思路：递推。dp（i，j）表示最优，那么即dp（i-1，j-1）+1最优，如果K层没有破，

ゝ一世哀愁。/ 2022年08月18日 02:41/ 0 赞/ 87 阅读

相关山东省第一届ACM大学生程序设计竞赛-Balloons（搜索）

问题及代码： Balloons Time Limit: 1000MS Memory limit: 65536K 题目描述 Both Saya and Kud

た入场券/ 2022年07月25日 15:52/ 0 赞/ 178 阅读

相关 ACM dp Cheapest Palindrome

POJ 3280 Cheapest Palindrome ![20170722100609554][] ![20170722100629840][] 题目大意：（带入样例

左手的ㄟ右手/ 2022年06月12日 11:16/ 0 赞/ 87 阅读

相关 ACM DP Dropping water balloons

滴，集训第十七天打卡。感觉这阵子都是dp啊... uva 10934 Dropping water balloons ![20170804101501032][

蔚落/ 2022年06月11日 09:36/ 0 赞/ 63 阅读

相关 ACM DP Partitioning by Palindromes

滴，集训第十六天打卡。补题路漫漫呀~ uva 11584 Partitioning by Palindromes ![20170803154641350][]

爱被打了一巴掌/ 2022年06月11日 08:47/ 0 赞/ 84 阅读

相关 ACM DP Max Sum Plus Plus

滴，集训第十三天打卡。今天依旧是DP专题，但是下午去玲珑杯划了会水，还打铁了... 委屈，感觉还是DP比较亲热。 HDU 1024 Max Sum Plus Plus

我会带着你远行/ 2022年06月11日 03:54/ 0 赞/ 109 阅读

相关 ACM DP Super Jumping! Jumping! Jumping!

滴，集训第十二天打卡。这两天是DP，划水了一天的简单题，嘻嘻。 HDU 1087 Super Jumping! Jumping! Jumping! ![2017072

秒速五厘米/ 2022年06月11日 03:37/ 0 赞/ 92 阅读

相关 ACM DP 石子合并问题

滴，集训第二十一天打卡。可能是对组队不太满意，都不大高兴做新的训练... 所以最近一直在磨DP，翻一下博客，发现最近都是DP啊... 这个石子合并的，我做的训练数据n是

小灰灰/ 2022年06月10日 01:17/ 0 赞/ 152 阅读

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

题意：k个水球，现在在一个n层建筑物上，水球可能在某一层层以上扔下去会破掉，现在求一个最少的次数使得用这k个水球能确定出哪一层。分析：假设你有无数个水球的情况下，那么

逃离我推掉我的手/ 2021年12月14日 20:29/ 0 赞/ 122 阅读