空间范围, 空间范围

1102 采药

二零零六年NOIP全国际缔盟赛广泛组

时限: 1 s

空间限制: 12柒仟 KB

标题品级 : 白银 Gold

 

 

 

题目陈述 Description

辰辰是个天资聪颖的孩子,他的企盼是成为世界上最宏大的医生。为此,他想拜周边最有威望的大夫为师。医务职员为了认清他的天赋,给他出了三个问题。医生把她带到三个内地都以中草药的隧洞里对他说:“孩子,那个岩洞里有局部比不上的药材,采每一株都亟需有个别光阴,每一株也可以有它本人的价值。笔者会给您一段时间,在这段时光里,你能够采到一些中草药。尽管你是多个精明能干的儿女,你应有能够让采到的中草药的总价值最大。”

万一您是辰辰,你能做到这一个任务吗?

输入描述 Input Description

输入第一行有几个整数T(1<=T<=1000)和M(1<=M<=100),用贰个空格隔断,T代表总共能够用来采药的日子,M代表山洞里的中中药材的多寡。接下来的M行每行李包裹罗两个在1到100里头(满含1和100)的卡尺头,分别代表采撷某株中药的年华和那株中药的价值。

出口描述 Output Description

输出包罗一行,这一行只含有二个莫西干发型,表示在分明的光阴内,可以采到的中药的最大总价值。

样例输入 萨姆ple Input

70 3

71 100

69 1

1 2

样例输出 萨姆ple Output

3

数量范围及提醒 Data Size & Hint

【数据规模】

对于30%的数据,M<=10;

对此全体的数据,M<=100。

1102 采药

二〇〇六年NOIP全国际缔盟赛广泛组

 时限: 1
s

 空间范围: 12捌仟KB

 题目品级 : 黄金Gold

 

 

标题汇报 Description

辰辰是个天资聪颖的男女,他的希望是形成世界上最伟大的医务人士。为此,他想拜周边最有威望的医务职员为师。医务人士为了认清她的天资,给她出了二个难点。医务卫生职员把他带到三个随地都以中草药的山洞里对她说:“孩子,那个洞穴里有部分不一的中药,采每一株都急需有的时刻,每一株也会有它本人的股票总市值。作者会给您一段时间,在近些日子里,你能够采到一些中药。如若您是一个智慧的孩子,你应有能够让采到的中药的总价值最大。” 

一旦你是辰辰,你能一气浑成那些职务吗?

输入描述 Input Description

输入第一行有四个整数T(1<=T<=一千)和M(1<=M<=100),用一个空格隔绝,T代表总共可以用来采药的年华,M代表山洞里的药材的多少。接下来的M行每行李包裹罗多个在1到100中间(包蕴1和100)的整数,分别表示采撷某株中药的小时和那株中草药的市场总值。

出口描述 Output Description

输出包蕴一行,这一行只含有贰个卡尺头,表示在鲜明的大运内,能够采到的药材的最大总价值。

样例输入 Sample Input

70 3

71 100

69 1

1 2

样例输出 Sample Output

3

多少范围及提醒 Data Size & Hint

【数据规模】

对于30%的数据,M<=10;

对于整个的数据,M<=100。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int N = 110 ;
 8 
 9 int f[N][1010];
10 int ti[N];
11 int ji[N];
12 int t,m,n;
13 
14 int main()
15 {
16     scanf("%d%d",&t,&m);
17     for(int i = 1;i <= m; ++i)
18         scanf("%d%d",&ti[i],&ji[i]);
19     for(int i = 1;i <= m; ++i)
20     {
21         for(int j = 0 ;j <= t; ++j)
22         {
23             if(j>=ti[i]) f[i][j] = max(f[i-1][j] , f[i-1][j-ti[i]] + ji[i]);
24             else f[i][j] = f[i-1][j] ;
25         }
26     }
27     printf("%d",f[m][t]);
28     return 0;
29 }

 

分拣标签 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 }

 

相关文章

网站地图xml地图