P1048 采药

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{ int time,value;};
 4 int dp[1001][1001]={0};
 5 int main()
 6 {
 7     node array[1000];
 8     int t,m;
 9     cin>>t>>m;
10     for(int i=1;i<=m;i++){
11         cin>>array[i].time>>array[i].value;
12     }
13     for(int i=1;i<=m;i++){
14         for(int j=0;j<=t;j++){
15             if(array[i].time>j){
16                 dp[i][j]=dp[i-1][j];
17             }
18             else{
19                 dp[i][j]=max(dp[i-1][j],
20                     dp[i-1][j-array[i].time]+array[i].value);
21             }
22         }
23     }
24     cout<<dp[m][t];
25 }