空间限制,题目叙述 Description

1102 采药

二〇〇五年NOIP全国联赛普及组

时间限制: 1 s

空间范围: 128000 KB

题目等级 : 黄金 高尔德(Gold)

 

 

 

题目叙述 Description

辰辰是个天资聪颖的儿女,他的冀望是成为世界上最光辉的先生。为此,他想拜附近最有威望的卫生工作者为师。医生为了判定她的天分,给他出了一个难题。医生把她带到一个无处都是中药的洞穴里对他说:“孩子,那些洞穴里有一些两样的药材,采每一株都亟需有些光阴,每一株也有它本身的价值。我会给你一段时间,在那段时光里,你可以采到一些药材。倘诺你是一个精明能干的子女,你应有可以让采到的中草药的总价值最大。”

一经您是辰辰,你能到位那些义务吗?

输入描述 Input Description

输入第一行有四个整数T(1<=T<=1000)和M(1<=M<=100),用一个空格隔开,T代表总共可以用来采药的时刻,M代表山洞里的药材的数量。接下来的M行每行包含七个在1到100中间(包蕴1和100)的整数,分别表示采摘某株中草药的时光和那株中草药的市值。

输出描述 Output Description

输出包蕴一行,这一行只含有一个整数,表示在规定的时刻内,可以采到的中中药材的最大总价值。

样例输入 萨姆(Sam)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

 空间限制: 128000
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。

 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地图