P1048 采药

admin

https://www.luogu.org/problemnew/show/P1048

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

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

输入输出格式
输入格式：
第一行有 2 个整数 T(1≤T≤1000) 和 M(1≤M≤100) ，用一个空格隔开， T 代表总共能够用来采药的时间， M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100 ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式：
1 个整数，表示在规定的时间内可以采到的草药的最大总价值。

输入输出样例
输入样例#1：
70 3
71 100
69 1
1 2

输出样例#1：
3
说明
对于30%的数据， M≤10 ；

对于全部的数据， M≤100 。

NOIP2005普及组第三题

Scorpio

1. #include<iostream>
   
2. using namespace std;
   
3. int w[105],v[105],dp[1005];
   
4. int t,m,i,j;
   
5. int main()
   
6. {
   
7.     cin>>t>>m;
   
8.     for(int i=1;i<=m;i++)
   
9.         cin>>w[i]>>v[i];
   
10.     for(i=1;i<=m;i++)
    
11.         for(j=t;j>=0;j--)
    
12.             if(j>=w[i])
    
13.                 dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
    
14.     cout<<dp[t];
    
15.     return 0;
    
16. }
    

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int m,t,v[200],c[200],f[200][1200];
   
4. int i,j;
   
5. int main()
   
6. {
   
7.     cin>>t>>m;
   
8.     for(i=1;i<=m;i++)
   
9.         cin>>c[i]>>v[i];
   
10.     for(i=1;i<=m;i++)
    
11.     {
    
12.         for(j=1;j<=t;j++)
    
13.         {
    
14.             f[i][j]=f[i-1][j];
    
15.             if(j>=c[i])
    
16.                 f[i][j]=max(f[i][j],f[i-1][j-c[i]]+v[i]);
    
17.         }
    
18.     }
    
19.     cout<<f[m][t];
    
20.     return 0;
    
21. }
    

复制代码

zhwang

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int c[101];
   
5. int v[101];
   
6. int f[1001];
   
7. int main()
   
8. {
   
9.     int t,m;
   
10.     scanf("%d%d",&t,&m);
    
11.     for(int i=1;i<=m;i++)
    
12.     {
    
13.         scanf("%d%d",&c[i],&v[i]);
    
14.     }
    
15.     for(int i=1;i<=m;i++)
    
16.     {
    
17.         for(int j=t;j>=c[i];j--)
    
18.         {
    
19.             f[j]=max(f[j],f[j-c[i]]+v[i]);
    
20.         }
    
21.     }
    
22.     printf("%d",f[t]);
    
23.     return 0;
    
24. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int T,M,maxn;
   
4. int t[101],w[100],dp[101][1001];
   
5. int main()
   
6. {
   
7.     cin>>T>>M;
   
8.     for(int i=1;i<=M;i++)cin>>t[i]>>w[i];
   
9.     for(int i=1;i<=M;i++)
   
10.         for(int j=1;j<=T;j++)
    
11.             if(t[i]<=j)dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+w[i]);
    
12.             else dp[i][j]=dp[i-1][j];
    
13.     for(int j=1;j<=T;j++)maxn=max(maxn,dp[M][j]);
    
14.     cout<<maxn;
    
15.     return 0;
    
16. }
    

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int maxv,n;
   
4. int w[150],v[150],i,j,dp[1010];
   
5. int main()
   
6. {
   
7.     cin>>maxv>>n;
   
8.     for (i=1;i<=n;i++) cin>>w[i]>>v[i];
   
9.     for (i=1;i<=n;i++)
   
10.         for (j=maxv;j>=w[i];j--)
    
11.             dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    
12.     cout<<dp[maxv];
    
13.     return 0;
    
14. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. int f[101][1001],cost[101],get[101],t,n,sum=0;
   
3. int max(int a,int b)
   
4. {
   
5.     if(a>=b)
   
6.         return a;
   
7.     else
   
8.         return b;
   
9. }
   
10. int main()
    
11. {
    
12.     scanf("%d%d",&t,&n);
    
13.         for(int i=1;i<=n;i++)
    
14.                 scanf("%d%d",&cost[i],&get[i]);
    
15.         for(int i=1;i<=n;i++)  
    
16.         for(int v=0;v<=t;v++)
    
17.         {  
    
18.             f[i][v]=f[i-1][v];  
    
19.             if(v>=cost[i])  
    
20.                 f[i][v]=max(f[i-1][v],f[i-1][v-cost[i]]+get[i]);   
    
21.         }  
    
22.         printf("%d",f[n][t]);
    
23.     return 0;
    
24. }

复制代码

吴语林

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <set>
   
7. using namespace std;
   
8. int t,n,w[200]={0},v[200]={0},f[1000]={0};
   
9. int main()
   
10. {
    
11.     scanf("%d%d",&t,&n);
    
12.     for(int i=1;i<=n;i++)
    
13.             scanf("%d%d",&w[i],&v[i]);
    
14.     for(int i=1;i<=n;i++)
    
15.                 for(int j=t;j>=w[i];j--)
    
16.                         f[j]=max(f[j],f[j-w[i]]+v[i]);
    
17.         printf("%d",f[t]);
    
18.     return 0;
    
19. }

复制代码

Scorpio

1. #include<iostream>
   
2. using namespace std;
   
3. int f[1005],v[105],w[105];
   
4. int i,j,t,m;
   
5. int main()
   
6. {
   
7.     cin>>t>>m;
   
8.     for(i=1;i<=m;i++)
   
9.         cin>>v[i]>>w[i];
   
10.     for(i=1;i<=m;i++)
    
11.         for(j=t;j>=v[i];j--)
    
12.             f[j]=max(f[j-v[i]]+w[i],f[j]);
    
13.     cout<<f[t];
    
14.     return 0;
    
15. }

复制代码

罗笛晓

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=105;
   
4. int t[mm],v[mm],f[1005];
   
5. int T,M;
   
6. int main()
   
7. {
   
8.     cin>>T>>M;
   
9.     f[0]=0;
   
10.     for(int i=1;i<=M;i++)cin>>t[i]>>v[i];
    
11.     for(int i=1;i<=M;i++)
    
12.         for(int j=T;j>=t[i];j--)
    
13.             f[j]=max(f[j],f[j-t[i]]+v[i]);
    
14.             //for(int i=0;i<=T;i++)cout<<f[i]<<" ";
    
15.             cout<<f[T];
    
16.     return 0;
    
17. }

复制代码