[LUOGU] P1048 采药
2024-10-20 08:27:15
题目描述
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入输出格式
输入格式:
输入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式:
输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
输入输出样例
输入样例#1: 复制
70 3
71 100
69 1
1 2
输出样例#1: 复制
3
说明
对于30%的数据,M <= 10;
对于全部的数据,M <= 100。
NOIP2005普及组第三题
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]
对应情况 1:不选第i件物品,则i-1件组成j个体积
对应情况 2:选择第i件物品,则i-1件组成j-v[i]个体积,且总价值加w[i]
注意当v[i]>=j时,直接转移f[i][j]=f[i-1][j]
//Writer:GhostCai && His Yellow Duck
#include<iostream>
using namespace std;
const int MAXN=1005;
int dp[MAXN][MAXN],V,w[MAXN],v[MAXN];
int m,n;
int ans;
int main(){
cin>>V>>n;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
if(v[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else dp[i][j]=dp[i-1][j];
}
}
// for(int i=1;i<=V;i++) ans=max(ans,dp[n][i]);
ans=dp[n][V];
cout<<ans;
}
最新文章
- Qt qml 模拟iphone slide to unlock 的聚光动画文字效果
- 数据结构:后缀自动机 WJMZBMR讲稿的整理和注释
- asp.net 捕获throw
- Maven使用笔记(六)使用Maven进行多模块拆分
- 【转载】MySQL性能优化的最佳20+条经验
- Arrays.toString Arrays.asList
- linux 下安装gsl
- <;十二>;面向对象分析之UML核心元素之节点和设备
- 向linux内核版本号添加字符/为何有时会自动添加“+”号
- Autofac 依赖注入 ASP.NET MVC5 插件机制中插件的简单实现
- python获取系统时间
- 不实名认证去除新浪云SEA的实名认证提示的方法
- CSS注释代码
- Android入门——UI(8)——Fragment(2)
- 移动开发平台-应用之星app制作教程
- BZOJ3036绿豆蛙的归宿
- Leetcode刷题C#版之Toeplitz Matrix
- Java知多少(26)源文件的声明规则
- Android学习笔记PreferenceFragment的使用
- 【DSU on tree】【CF741D】Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
热门文章
- assembly x86(nasm)子程序1
- Linux权限相关
- [Noip2012普及组]摆花
- spring boot 配置https 报这个错误:java.lang.IllegalArgumentException: Private key must be accompanied by certificate chain
- hdu6318( 2018 Multi-University Training Contest 2)
- python之函数名,闭包、迭代器
- 20180607pip install xxx报错SyntaxError invalid syntax
- HashMap的小总结 + 源码分析
- AtCoder D - 高橋君と見えざる手 / An Invisible Hand 简单思维题
- python_19(Django外键)