小飞侠的游园计划

 1 #include <iostream>
 2 using namespace std;
 3 const int maxn=1005;
 4 struct node
 5 {
 6     int time;
 7     int like;
 8 };
 9  
10 int max(int a,int b)
11 {
12     return a>b?a:b;
13 }
14 int main()
15 {
16     node k[maxn];
17     int n,m,i,j;            //n是娱乐项目数，m是总时间;
18     cin>>n>>m;
19     for(i=0;i<n;i++)
20         cin>>k[i].like>>k[i].time;      //输入喜欢程度和时间；
21     int sum[maxn]={0};
22     for(i=0;i<n;i++)
23     //    for(j=1;j<=m;j++)
24         for(j=m;j>=k[i].time;j--)
25             sum[j]=max(sum[j],sum[j-k[i].time]+k[i].like);   //对于某个活动，只有选或者不选，选的话，时间上就要减去该活动耗费的时间，价值上加上该活动的价值；
26         cout<<sum[m]<<endl;
27         return 0;
28 }