疯狂的采药 【完全背包】

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=1e5+100;
 4 using namespace std;
 5 int T,M,sum;
 6 int val[N],c[N];
 7 int f[N];
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
11     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 inline void write(int x){
15      char F[200];
16      int tmp=x>0?x:-x ;
17      if(x<0)putchar(‘-‘) ;
18      int cnt=0 ;
19         while(tmp>0)
20         {
21             F[cnt++]=tmp%10+‘0‘;
22             tmp/=10;
23         }
24         while(cnt>0)putchar(F[--cnt]) ;
25 }
26 int main()
27 {
28     T=read(),M=read();
29     for(int i=1;i<=M;i++){
30         c[i]=read(),val[i]=read();
31         sum+=c[i];
32     }
33     memset(f,0,sizeof(f));
34     f[0]=0;//一定要初始化 
35     for(int i=1;i<=M;i++){
36         for(int j=c[i];j<=T;j++){//一定要写正循环，因为每件物品可以取无限次 
37             f[j]=max(f[j],f[j-c[i]]+val[i]);
38         }
39     }
40     printf("%d\n",f[T]);
41     return 0;
42 }