P1616 疯狂的采药

admin

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留给你！

吴语林

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. }

复制代码

type尧

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. }
    

复制代码

黄煦喆

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. }
    

复制代码

罗笛晓

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. }
    

复制代码

张笑宇

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. }

复制代码

七夜劫年

#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;
}

zhwang

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. }

复制代码

walk_alone

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. }

复制代码

Scorpio

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. }
    
16. 
    

复制代码