2005年NOIP全国联赛普及组

1102 采药 二零零六年NOIP全国际结盟赛普遍组，1102noip

1102 采药

2005年NOIP全国际缔盟赛普遍组

时限: 1 s
空中约束: 128000 KB 标题等第 : 黄金 Gold       标题叙述 Description

辰辰是个聪明非凡的子女，他的盼望是成为世界上最伟大的医师。为此，他想拜周围最有名望的医生为师。医务职员为了认清他的天分，给她出了三个难点。医生把她带到贰个四面八方都是中药的岩洞里对她说：“孩子，那几个石洞里有部分不相同的中药材，采每生机勃勃株都亟待部分时刻，每意气风发株也可能有它本身的市场总值。小编会给您生机勃勃段时间，在这里段日子里，你能够采到一些药材。要是您是贰个智慧的男女，你应有能够让采到的药材的总共价值最大。”

如若您是辰辰，你能乘热打铁那几个职务吗？

输入描述 Input Description

输入第生机勃勃行有几个整数T（1<=T<=1000卡塔尔国和M（1<=M<=100卡塔 尔（英语：State of Qatar），用三个空格隔开分离，T代表总共能够用来采药的小时，M代表山洞里的中中草药材的数额。接下来的M行每行包涵三个在1到100中间（富含1和100卡塔 尔（英语：State of Qatar）的莫西干发型，分别代表采撷某株中药的时日和那株中药的股票总值。

输出描述 Output Description

出口包括意气风发行，那大器晚成行只蕴含三个整数，表示在鲜明的时间内，能够采到的药材的最大总价。

样例输入 Sample Input

70 3

71 100

69 1

1 2

样例输出 萨姆ple Output

3

多少范围及提示 Data Size & Hint

【数据规模】

对于30%的数据，M<=10；

对此任何的数据，M<=100。

分拣标签 Tags 点此进行

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int timee[10001];
 6 int v[10001];
 7 int f[1001][1001];
 8 int main()
 9 {
10     int maxtime,n;
11     cin>>maxtime>>n;
12     for(int i=1;i<=n;i++)
13         cin>>timee[i]>>v[i];
14     for(int i=1;i<=n;i++)
15     {
16         for(int j=0;j<=maxtime;j++)
17         {
18             if(j>=timee[i])
19                 f[i][j]=max(f[i-1][j],f[i-1][j-timee[i]]+v[i]);
20             else
21             f[i][j]=f[i-1][j];
22         }
23     }
24     cout<<f[n][maxtime];
25     return 0;
26 }

 

采药 二零零七年NOIP全国际结盟赛广泛组，1102noip 1102 采药 2007年NOIP全国际联盟赛普遍组 时间约束: 1 s 空间范围: 128000 KB 标题品级: 白银 Gold 标题叙述...

本文由ag旗舰厅官网发布于关于计算机,转载请注明出处：2005年NOIP全国联赛普及组

关键词：