题目名称	68. [NOIP 2005]采药
输入输出	`medic.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2008-07-19加入
开放分组	全部用户
提交状态
分类标签	动态规划 NOIP/CSP 背包问题 01背包
	分享题解

通过：1141，提交：2292，通过率：49.78%
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
521	100	0.000 s	0.00 MiB	C++
cy	100	0.000 s	0.00 MiB	C++
莫知	100	0.000 s	0.00 MiB	C++
‎MistyEye	100	0.000 s	0.00 MiB	C++
rvalue	100	0.000 s	0.00 MiB	C++
面对疾风吧疾风疾风吧	100	0.000 s	0.00 MiB	C++
Hakurou!	100	0.000 s	0.00 MiB	C++
LCWhiStLe	100	0.000 s	0.00 MiB	C++
Ge0Bi1Lao0W	100	0.000 s	0.00 MiB	C++

本题关联比赛
暑假培训四
DP暑假B班欢乐水题赛
叫图论的DP题

关于采药的近10条评论(全部评论)
简简单单的背包 Komin 2021-10-05 16:14 32楼
数组开小了直接7个E。。。 :( 城南花已开 2020-08-13 23:08 31楼
cb 2020-04-20 10:19 30楼
夜莺 2020-02-06 15:14 29楼
01背包问题裸题没啥，随心 2019-07-27 00:12 28楼
若失若诗 2018-11-10 10:01 27楼
路过一只小渣逼面罩Mask 2018-11-08 20:18 26楼
路过 INFINITY 2018-10-27 11:22 25楼
200 8 79 83 58 14 86 54 11 79 28 72 62 52 15 48 68 62 2018noip必胜！ 2018-09-15 09:21 24楼
#include <iostream> #include <cstdio> using namespace std; int F(int a,int b) { if(a>b)return a; else return b; } int main(void) { //freopen("medic.in","r",stdin); //freopen("medic.out","w",stdout); int n = 0,v = 0;int r[9000]={0},w[9000]={0};int f[400][400]={0}; cin>>v>>n; for(int i = 1;i<n+1;i++) { cin>>r[i]>>w[i]; } for(int i=1;i<n+1;i++) for(int j = v;j>=r[i];j--) { f[i][j]=F(f[i-1][j],f[i-1][j-r[i]]+w[i]); } cout<<f[n][v]; } 2018noip必胜！ 2018-09-15 09:20 23楼

68. [NOIP 2005]采药

★☆ 输入文件：medic.in 输出文件：medic.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

【输入文件】

输入的第一行有两个整数$T(1\leq T\leq 1000)$和$M(1\leq M\leq 100)$，用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间(包括 $1$ 和 $100$)的整数，分别表示采摘某株草药的时间和这株草药的价值。

【输出文件】

输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

【样例输入】

【样例输出】

【数据规模】

对于30%的数据，$M\leq 10$；

对于100%的数据，$M\leq 100$。