按照发起人离开的时间从小到大排序，然后就是一个0-1背包问题，要注意的是活动持续时间小于j
1
#pragma warning(disable : 4786)
2#include<iostream>
3#include<string>
4#include<cstring>
5#include <algorithm>
6#include<vector>
7using namespace std;
8
9struct load
10
{
11
int h;
12 int l;
13 int t;
14
};
15load souc[31];
16bool cmp(const load &a,const load &b)
17{
18 return a.t < b.t;
19}
20int main()
21{
22 int n;
23 int i,j;
24 int maxv;
25 while (scanf("%d",&n)==1 && n>0)
26
{
27 vector <int> f;
28 maxv=0;
29 for (i=0;i<n;++i)
30 {
31 scanf("%d%d%d",&souc[i].h,&souc[i].l,&souc[i].t);
32 if (souc[i].t > maxv)
33 {
34 maxv = souc[i].t;
35
}
36 }
37 sort(souc,souc+n,cmp);
38 f.resize(maxv+1);
39 fill(f.begin(),f.end(),0);
40 int t=0;
41 for (i=0;i<n;++i)
42 {
43 for (j=maxv;j>=souc[i].l;--j)
44 {
45 if (souc[i].t >= j)
46 {
47 f[j] = f[j]>f[j-souc[i].l]+souc[i].h?f[j]:f[j-souc[i].l]+souc[i].h;
48 if (f[j] > t)
49 {
50 t = f[j];
51 }
52 }
53 }
54 }
55 cout<<t<<endl;
56 }
57 return 0;
58}
59
posted on 2011-05-18 17:39
mr_chen 阅读(132)
评论(0) 编辑 收藏 引用 所属分类:
动态规划