uva 10154 - Weights and Measures【dp】qi

曾经终败给现在 2022-08-12 03:00 105阅读 0赞

题意：[uva 10154 - Weights and Measures][]

题意：有一些乌龟有一定的体重和力量，求摞起来的最大高度、力量必须承受其上面包括自己的全部的重量。

分析：先按其能举起来的力量从小到大排序

然后定义dp【i】 表示摞起来 i 只乌龟的最小质量。

然后转移就是每次用遍历O（n）的复杂度找最小的，然后记录，保存最大值即可。

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <map>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int N = 10050;
    struct Node
    {
        int w,pow;
    };
    vector<Node> v;
    int cmp(Node a,Node b)
    {
        if(a.pow!=b.pow)
            return a.pow<b.pow;
    }
    int dp[N];  //dp[i] 选出i个乌龟摞起来的最小重量
    int main()
    {
        Node x;
        while(~scanf("%d%d",&x.w,&x.pow)){
            x.pow-=x.w;
            v.push_back(x);
        }
        sort(v.begin(),v.end(),cmp);
        memset(dp,0x3f3f3f3f,sizeof(dp));
        int ans=0;
        dp[0]=0;
        for(int i=0;i<v.size();i++)
        {
             for(int  j=v.size()-1; j>=1; j--)
            {
                if( dp[j-1]<=v[i].pow)
                    dp[j] =min( dp[j], dp[j-1]+v[i].w);
                if( dp[j]<1000000000 )
                    ans =max( j,ans);
            }
        }
        printf("%d\n",ans);
        v.clear();
        return 0;
    }

[uva 10154 - Weights and Measures]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1095

发表评论取消回复

表情：

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

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

相关阅读

相关 UVA 822 Queue and A

题目链接：[https://vjudge.net/problem/UVA-822][https_vjudge.net_problem_UVA-822] 翻译摘自：《算法禁赛入

桃扇骨/ 2023年06月04日 14:54/ 0 赞/ 43 阅读

相关 uva 10154 - Weights and Measures【dp】qi

题意：[uva 10154 - Weights and Measures][] 题意：有一些乌龟有一定的体重和力量，求摞起来的最大高度、力量必须承受其上面包括自己的

曾经终败给现在/ 2022年08月12日 03:00/ 0 赞/ 106 阅读

相关 uva 11491——Erasing and Winning

题意：给定一个n位的整数，要求从中去掉k位，使得剩下的数字最大。思路：单调队列。在满足删除的数等于k 的前提下求一个不敌减的序列。 code：

太过爱你忘了你带给我的痛/ 2022年08月09日 16:36/ 0 赞/ 97 阅读

相关 uva 10673 ——Play with Floor and Ceil

题意：给定两个数n和m，对于n/m一个向上取整，一个向下取整，然后得到一个方程即P\floor(n/m）+q\ceil(n/m)=n; 求该公式中p和q的值的大小。

太过爱你忘了你带给我的痛/ 2022年08月09日 13:49/ 0 赞/ 122 阅读

相关 Cows and Cars UVA - 10491——初级概率题目

Think: 1>题意理解:假若有三个门，你如果一开始选了牛，然后可以换的时候直接换，那么最后得到车的概率就是最初选了牛的概率:现在题目扩展，有n头牛，m辆车，

蔚落/ 2022年06月15日 11:41/ 0 赞/ 104 阅读

相关 uva 11029 - Leading and Trailing(快速幂）

[题目链接：uva 11029 - Leading and Trailing][uva 11029 - Leading and Trailing] 题目大意：给出一

阳光穿透心脏的1/2处/ 2022年05月14日 13:50/ 0 赞/ 79 阅读

相关 uva 10491 - Cows and Cars（概率）

[题目连接：uva 10491 - Cows and Cars][uva 10491 - Cows and Cars] 题目大意：给出a，b和c，表示有a + b

深藏阁楼爱情的钟/ 2022年05月12日 22:14/ 0 赞/ 103 阅读

相关 uva 10375 - Choose and divide(组合数）

[题目连接：uva 10375 - Choose and divide][uva 10375 - Choose and divide] 题目大意：给出p，q，s和r

Love The Way You Lie/ 2022年05月12日 22:14/ 0 赞/ 124 阅读

相关 uva10635Prince and Princess(LIS)

题意：求最长相同公共子序列。分析：《训练指南》P66，本题是一道经典的题目，巧妙的将LCS问题转化为LIS问题。这种题目的一个特定就是其中一个序列的所有元素均不相同。

Dear 丶/ 2021年12月17日 03:17/ 0 赞/ 202 阅读

相关 CF1088F Ehab and a weird weight formula

[CF1088F Ehab and a weird weight formula][CF1088F_Ehab and a weird weight formula] 推性质

ゞ浴缸里的玫瑰/ 2021年11月13日 15:38/ 0 赞/ 164 阅读