uva 10934—— Dropping water balloons

ゝ一世哀愁。 2022-08-18 02:41 86阅读 0赞

题意：给定K个气球，然后n层楼的高度，求确定气球的硬度（站在多高能摔破）

思路：递推。dp（i，j）表示最优，那么即dp（i-1，j-1）+1最优，如果K层没有破，则把K+1看成1层继续。得到转移方程dp（i，j）=k+dp(i,j-1)=dp(i-1,j-1)+dp(i,j-1);

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=9999999;
    const int inf=-INF;
    const int N=125;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int k,ans;
    ll n,dp[N][N];
    int main()
    {
        while (~scanf("%d%lld",&k,&n),k)
        {
            cls(dp,0);k=min(k,63);ans=-1;
            ft(i,1,63) ft(j,1,63)
                dp[i][j]=dp[i-1][j-1]+1+dp[i][j-1];
            ft(i,1,63)
            if (dp[k][i]>=n) {ans=i;break;}
            if(ans>-1) printf("%d\n",ans);
            else puts("More than 63 trials needed.");
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Dropping Balls 小球下落 UVA 679

解题思路：本题数据比较大，所以不采取数组储存；题目中的小球个数 I 如果为奇数时，它往左边走的小球个数是（I+1）/2个；偶数是往右边 I/2个。 1. \include<

比眉伴天荒/ 2024年02月17日 18:50/ 0 赞/ 10 阅读

相关小球下落(Dropping Balls,UVa 679)题解

文章目录题目描述输入输出原题（PDF）算法分析解题标程 ------------------

╰+哭是因爲堅強的太久メ/ 2022年12月28日 07:22/ 0 赞/ 146 阅读

相关 uva 10934—— Dropping water balloons

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

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

相关 Balloon Comes!

Balloon Comes! Time Limit: 1000ms Memory limit: 65535K 有疑问？点这里^\_^ 题目描述 The con

浅浅的花香味﹌/ 2022年08月10日 05:50/ 0 赞/ 115 阅读

相关 uva679 Dropping Balls

A number ofKballs are dropped one by one from the root of a fully binary tree structure

比眉伴天荒/ 2022年07月12日 12:23/ 0 赞/ 89 阅读

相关 ACM DP Dropping water balloons

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

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

相关 UVA - 679 Dropping Balls

题目描述 [https://vjudge.net/problem/UVA-679][https_vjudge.net_problem_UVA-679] 仔细观察规律模拟处理

柔情只为你懂/ 2022年05月09日 05:03/ 0 赞/ 73 阅读

相关 Burst Balloons

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on

偏执的太偏执、/ 2021年12月17日 10:27/ 0 赞/ 158 阅读

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

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

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

相关 UVA 11292 - The Dragon of Loowater (water)

[http://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&category=24&page=

柔情只为你懂/ 2021年11月19日 15:44/ 0 赞/ 109 阅读