华师一附中OI组

标题: P1616 疯狂的采药 [打印本页]
作者: admin    时间: 2018-5-17 17:27
标题: P1616 疯狂的采药
https://www.luogu.org/problemnew/show/P1616

题目背景
此题为NOIP2005普及组第三题的疯狂版。

此题为纪念LiYuxiang而生。

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

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

此题和原题的不同点：

1.每种草药可以无限制地疯狂采摘。

2.药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

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

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

输入输出样例
输入样例#1：
70 3
71 100
69 1
1 2
输出样例#1：
140
说明
对于30%的数据，M <= 1000；

对于全部的数据，M <= 10000，且M*T<10000000(别数了，7个0)。

加油LiYuxiang，第一个AC留给你！
作者: Scorpio    时间: 2018-7-8 19:44
  1. #include<iostream>
  2. using namespace std;
  3. int f[105000],w[10500],v[10500];
  4. int n,m,i,j;
  5. int main()
  6. {
  7.     cin>>n>>m;
  8.     for(i=1;i<=m;i++)
  9.         cin>>w[i]>>v[i];
  10.     for(i=1;i<=m;i++)
  11.         for(j=w[i];j<=n;j++)
  12.             f[j]=max(f[j-w[i]]+v[i],f[j]);
  13.     cout<<f[n];
  14.     return 0;
  15. }

复制代码
作者: walk_alone    时间: 2018-7-27 21:47
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int f[10000001],cost[100001],w[100001];
  5. int main()
  6. {
  7.         int n,t;
  8.         scanf("%d%d",&t,&n);
  9.         for(int i=1;i<=n;i++)
  10.                 scanf("%d%d",&cost[i],&w[i]);
  11.         for(int i=1;i<=n;i++)
  12.                 for(int j=cost[i];j<=t;j++)
  13.                         f[j]=max(f[j],f[j-cost[i]]+w[i]);
  14.         printf("%d",f[t]);
  15.         return 0;
  16. }
复制代码
作者: zhwang    时间: 2018-7-27 22:12
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. int f[100000+100];
  5. int t,m;
  6. int timemiao[100001];
  7. int v[100001];
  8. int main()
  9. {
  10.         scanf("%d%d",&t,&m);
  11.         for(int i=1;i<=m;i++)
  12.         {
  13.                 scanf("%d%d",&timemiao[i],&v[i]);
  14.         }
  15.         for(int i=1;i<=m;i++)
  16.         {
  17.                 for(int j=1;j<=t;j++)
  18.                 {
  19.                         if(j-timemiao[i]<0)
  20.                         {
  21.                                 continue;
  22.                         }
  23.                         f[j]=max(f[j],f[j-timemiao[i]]+v[i]);
  24.                 }
  25.         }
  26.         printf("%d",f[t]);
  27.         return 0;
  28. }
复制代码
作者: 七夜劫年    时间: 2018-7-27 22:46
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int t,m;
int w[100001],s[100001],d[100001];
int maxn=0;
int main()
{
        cin>>t>>m;
       
        for(int i=1;i<=m;i++)
        {
                cin>>s[i]>>w[i];
        }
       
        for(int i=1;i<=m;i++)
        {
                for(int j=s[i];j<=t;j++)
                {
                        if( d[j] < d[j-s[i]]+w[i] ) d[j]=d[j-s[i]]+w[i];
                       
                        if( maxn < d[j] )
                        {
                                maxn=d[j];
                        }
                }
        }
       
        cout<<maxn<<endl;
        return 0;
}
作者: 张笑宇    时间: 2018-7-28 10:44
  1. #include<iostream>
  2. using namespace std;
  3. int maxv,n;
  4. int w[10010],v[10010],i,j,dp[100010];
  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=w[i];j<=maxv;j++)
  11.                 dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  12.         cout<<dp[maxv];
  13.         return 0;
  14. }
复制代码
作者: 吴语林    时间: 2018-7-29 19:40
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. int n,t,f[1000001],v,w;
  14. int main()
  15. {
  16.         scanf("%d%d",&t,&n);
  17.         for(int i=1;i<=n;i++)
  18.         {
  19.                 scanf("%d%d",&w,&v);
  20.                 for(int j=w;j<=t;j++)
  21.                         f[j]=max(f[j],f[j-w]+v);
  22.         }
  23.         printf("%d",f[t]);
  24.     return 0;
  25. }
复制代码
作者: 罗笛晓    时间: 2018-10-3 14:24
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mm=10005;
  4. int t[mm],v[mm],f[100005];
  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[i];j<=T;j++)
  13.             f[j]=max(f[j],f[j-t[i]]+v[i]);
  14.            cout<<f[T];
  15.     return 0;
  16. }
复制代码
作者: 黄煦喆    时间: 2018-10-4 09:58
  1. #include<iostream>
  2. using namespace std;
  3. int n,m;
  4. int t,v,dp[100001];
  5. int main()
  6. {
  7.     cin>>m>>n;
  8.     for(int i=1;i<=n;i++)
  9.     {
  10.         cin>>t>>v;
  11.         for(int j=t;j<=m;j++)dp[j]=max(dp[j],dp[j-t]+v);
  12.     }
  13.     cout<<dp[m];
  14.     return 0;
  15. }
复制代码
作者: type尧    时间: 2018-11-4 19:01
  1. //
  2. #include<bits/stdc++.h>
  3. #define maxm 10010
  4. #define maxt 100010
  5. using namespace std;
  6. int m,t;
  7. int ti[maxm];
  8. int price[maxm];
  9. int f[maxt];
  10. void getdata()
  11. {
  12.         cin>>t>>m;
  13.         for(int i=1;i<=m;i++){
  14.                 cin>>ti[i]>>price[i];
  15.         }
  16.         return;
  17. }
  18. void dp()
  19. {
  20.         for(int i=1;i<=m;i++)
  21.                 for(int j=ti[i];j<=t;j++)
  22.                         f[j]=max(f[j],f[j-ti[i]]+price[i]);
  23.         return;
  24. }
  25. int main()
  26. {
  27.         getdata();
  28.         dp();
  29.         cout<<f[t];
  30.         return 0;
  31. }
复制代码




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