Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >P1510 精卫填海

P1510 精卫填海

作者头像
attack
发布于 2018-04-12 06:57:46
发布于 2018-04-12 06:57:46
56800
代码可运行
举报
运行总次数:0
代码可运行

题目描述

【版权说明】

本题为改编题。

【问题描述】

发鸠之山,其上多柘木。有鸟焉,其状如乌,文首,白喙,赤足,名曰精卫,其名自詨。是炎帝之少女,名曰女娃。女娃游于东海,溺而不返,故为精卫。常衔西山之木石,以堙于东海。——《山海经》

精卫终于快把东海填平了!只剩下了最后的一小片区域了。同时,西山上的木石也已经不多了。精卫能把东海填平吗?

事实上,东海未填平的区域还需要体积为v的木石才可以填平,而西山上的木石还剩下n块,每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了,她也很累了,她还剩下的体力为c。

输入输出格式

输入格式:

输入文件的第一行是三个整数:v、n、c。

从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式:

输出文件只有一行,如果精卫能把东海填平,则输出她把东海填平后剩下的最大的体力,否则输出’Impossible’(不带引号)。

输入输出样例

输入样例#1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
【样例输入1100 2 10
50 5
50 5

【样例输入210 2 1
50 5
10 2

输出样例#1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
【样例输出10

【样例输出2】
Impossible

说明

【数据范围】

对于20%的数据,0<n<=50。

对于50%的数据,0<n<=1000。

对于100%的数据,0<n<=10000,所有读入的数均属于[0,10000],最后结果<=c。

比较简单的01背包问题,

1.这题写二维的会炸空间

2.我们可以在进行背包的过程中取到答案

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=10001;
 8 void read(int &n)
 9 {
10     char c='+';int x=0;bool flag=0;
11     while(c<'0'||c>'9')
12     {c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')
14     {x=x*10+(c-48);c=getchar();}
15     flag==1?n=-x:n=x;
16 }
17 int nedv,n,tl;
18 struct node
19 {
20     int v;
21     int w;
22 }stone[MAXN];
23 int dp[10001];
24 int ans=-1;
25 int main()
26 {
27     read(nedv);read(n);read(tl);
28     for(int i=1;i<=n;i++)
29     {
30         read(stone[i].v);
31         read(stone[i].w);
32     }
33     for(int i=1;i<=n;i++)
34     {
35         for(int j=tl;j>=stone[i].w;j--)
36         {
37             dp[j]=max(dp[j],dp[j-stone[i].w]+stone[i].v);
38             if(dp[j]>nedv)
39                 ans=max(ans,tl-j);
40         }
41     }
42     ans==-1?printf("Impossible"):printf("%d",ans);
43     return 0;
44 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
P1478 陶陶摘苹果(升级版)
题目描述 又是一年秋季时,陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果,这次她有一个a公分的椅子。当他手够不着时,他会站到椅子上再试试。 这次与NOIp2005普及组第一题不同的是:陶陶之前搬凳子,力气只剩下s了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。 现在已知n个苹果到达地上的高度xi,椅子的高度a,陶陶手伸直的最大长度b,陶陶所剩的力气s,陶陶摘一个苹果需要的力气yi,求陶陶最多能摘到多少个苹果。 输入输出格式 输入格式: 第1行:两个数 苹果数n,力气
attack
2018/04/13
7860
洛谷P2851 [USACO06DEC]最少的硬币The Fewest Coins(完全背包+多重背包)
题目描述 Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receiv
attack
2018/04/13
9860
P1021 邮票面值设计
题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1~MAX之间的每一个邮资值都能得到。 例如,N=3,K=2,如果面值分别为1分、4分,则在1分~6分之间的每一个邮资值都能得到(当然还有8分、9分和12分);如果面值分别为1分、3分,则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3,K=2时,7分就是可以得到的连续的邮资最大值,所以MAX=7,面值分别为1分、3分。 输入输出格式
attack
2018/04/13
8650
动态规划专题——背包模型
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。
浪漫主义狗
2022/09/19
1.1K0
P1850 换教室
题目描述 对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中,有  节课程安排在 nn 个时间段上。在第  个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 上课,而另一节课程在教室  进行。 在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的   节安排好的课程。如果学生想更换第 节课程的教室,则需要提出申请。若申请通过,学生就可以在第 个时间段去教室 上课,否则仍然在教室  上课。 由于更换教
attack
2018/04/12
1.6K0
P1850 换教室
dp考试
a 【问题描述】 ?个物品 ,每个物品都有恰好两。第 ?种物品的体积和价值分别是 ??和??。 背包的体积为 ?,问在不超过背包体积的情况下最多能放进少价值物品。 ,问在不超过背包体积的情况下最多能放
attack
2018/04/13
1.2K0
背包九讲—-整理+例题[通俗易懂]
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。
全栈程序员站长
2022/08/03
1.1K0
背包九讲—-整理+例题[通俗易懂]
P1049 装箱问题
题目描述 有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30,每个物品有一个体积(正整数)。 要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。 输入输出格式 输入格式: 一个整数,表示箱子容量 一个整数,表示有n个物品 接下来n行,分别表示这n 个物品的各自体积 输出格式: 一个整数,表示箱子剩余空间。 输入输出样例 输入样例#1: 24 6 8 3 12 7 9 7 输出样例#1: 0 说明 NOIp2001普及组 第4题 比较裸的01
attack
2018/04/13
1.3K0
ACM刷题之路(二十三) HDU 1114 完全背包 Piggy-Bank
告诉你背包的容量N,和 M 件物品分别各自的体积和质量, 求背包剩余容量为0(即刚好填满)的时候,最小的质量。
Designer 小郑
2023/08/01
2330
洛谷P1450 [HAOI2008]硬币购物
题目描述 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。 输入输出格式 输入格式: 第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s 输出格式: 每次的方法数 输入输出样例 输入样例#1:  1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900 输出样例#1: 4 27 说明 di,s<=100000 tot<=1000 [HAOI2008] 首
attack
2018/04/11
5940
动态规划专题刷题记录③:背包问题
从上图中可以看出,01背包每次计算i时的状态只用到了i-1的状态,所有可以舍去i这一维,优化成一维dp。
Here_SDUT
2022/06/29
1.9K0
动态规划专题刷题记录③:背包问题
蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级
/*问题描述   每个物品有一定的体积(废话),不同的物品组合,装入背包会战用一定的总体积。 假如每个物品有无限件可用,那么有些体积是永远也装不出来的。为了尽量装满背包, 附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解,如果是有限解, 保证不超过2,000,000,000   如果是无限解,则输出0 输入格式   第一行一个整数n(n<=10),表示物品的件数   第2行到N+1行: 每件物品的体积(1<= <=500) 输出格式   一个整数ans,表示不能用这些物品得到的最大体积。 样例输入 3 3 6 10 样例输出 17 */
Fivecc
2022/11/21
2700
P1063 能量项链
题目描述 在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为 (Mars单位),新产生的珠子的头标记为m,尾标记为n
attack
2018/04/12
9000
P2051 [AHOI2009]中国象棋
题目描述 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧! 输入输出格式 输入格式: 一行包含两个整数N,M,之间由一个空格隔开。 输出格式: 总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。 输入输出样例 输入样例#1:
attack
2018/04/12
1.2K0
P1294 高手去散步
题目背景 高手最近谈恋爱了。不过是单相思。“即使是单相思,也是完整的爱情”,高手从未放弃对它的追求。今天,这个阳光明媚的早晨,太阳从西边缓缓升起。于是它找到高手,希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会,他已经准备好了一切。 题目描述 鳌头山上有n个观景点,观景点两两之间有游步道共m条。高手的那个它,不喜欢太刺激的过程,因此那些没有路的观景点高手是不会选择去的。另外,她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长(观景时它不会理高手),已知高手的穿
attack
2018/04/13
5490
P2690 接苹果
题目背景 USACO 题目描述 很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树(编号为1和2), 每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果,所以她只能等待苹果 从树上落下。但是,由于苹果掉到地上会摔烂,贝茜必须在半空中接住苹果(没有人爱吃摔烂的苹果)。贝茜吃东西很快,她接到苹果后仅用几秒钟就能吃完。每一分钟,两棵苹果树其中的一棵会掉落一个苹果。贝茜已经过了足够的训练, 只要站在树下就一定能接住这棵树上掉落的苹果。同时,贝茜能够在两棵树之间 快速移动(移动时间远少于1分钟),因此当苹果掉落时
attack
2018/04/12
6850
洛谷P1437 [HNOI2004]敲砖块(dp)
在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖,从上到下每层依次减少一块砖。每块砖
attack
2018/07/27
3130
P2871 [USACO07DEC]手链Charm Bracelet
题目描述 Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'de
attack
2018/04/13
5410
混合背包问题解法&示例(洛谷p1833)
混合背包问题是把01背包、完全背包、多重背包混在一起的问题,看着比较复杂,其实就是分而治之,转换为前面这三种背包问题即可。
灯珑LoGin
2023/10/18
3420
P2347 砝码称重
题目描述 设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000), 输入输出格式 输入格式: 输入方式:a1 a2 a3 a4 a5 a6 (表示1g砝码有a1个,2g砝码有a2个,…,20g砝码有a6个) 输出格式: 输出方式:Total=N (N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况) 输入输出样例 输入样例#1: 1 1 0 0 0 0 输出样例#1: Total=3 应该是01背包问题, 但是暴力居然过了! 1
attack
2018/04/13
5650
相关推荐
P1478 陶陶摘苹果(升级版)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验