华师一附中OI组

标题: P1048 采药 [打印本页]
作者: admin    时间: 2018-6-3 12:15
标题: P1048 采药
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    时间: 2018-7-4 08:39
  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. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-7-15 09:43
  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    时间: 2018-7-27 20:07
  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. }
复制代码
作者: 黄煦喆    时间: 2018-7-27 20:48
本帖最后由 黄煦喆 于 2018-7-27 20:49 编辑
  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. }
复制代码
作者: 张笑宇    时间: 2018-7-28 10:44
  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    时间: 2018-7-28 13:43
  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. }
复制代码
作者: 吴语林    时间: 2018-7-29 19:39
  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    时间: 2018-10-2 09:57
  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. }
复制代码
作者: 罗笛晓    时间: 2018-10-3 09:42
  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. }
复制代码
作者: admin    时间: 2019-10-15 20:14
标准的二维数组的DP
  1. #include<iostream>
  2. using namespace std;
  3. const int mm=110;
  4. const int mn=1100;
  5. int W,N;
  6. int w[mm],v[mm];
  7. int f[mn][mm];
  8. int i,j,k;
  9. int  main()
  10. {
  11.         cin>>W>>N;
  12.         for (i=1; i<=N; i++)  cin>>w[i]>>v[i];
  13.         for (k=1; k<=N; k++)
  14.                 for (int n=0; n<=W; n++)
  15.                         if (n<w[k])f[n][k]=f[n][k-1];
  16.                         else
  17.                                 f[n][k]=max(f[n][k-1],f[n-w[k]][k-1]+v[k]);
  18.         cout<<f[W][N];
  19.         return 0;
  20. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2