Jobdu-1499-项目安排[解题代码] | Acm之家

九度-1499-项目安排[解题代码] | Acm之家

小明每天都在开源社区上做项目，假设每天他都有很多项目可以选，其中每个项目都有一个开始时间和截止时间，假设做完每个项目后，拿到报酬都是不同的。由于小明马上就要硕士毕业了，面临着买房、买车、给女友买各种包包的鸭梨，但是他的钱包却空空如也，他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明，如何在最短时间内安排自己手中的项目才能保证赚钱最多（注意：做项目的时候，项目不能并行，即两个项目之间不能有时间重叠，但是一个项目刚结束，就可以立即做另一个项目，即项目起止时间点可以重叠）。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是一个整数n(1<=n<=10000)：代表小明手中的项目个数。
接下来共有n行，每行有3个整数st、ed、val，分别表示项目的开始、截至时间和项目的报酬，相邻两数之间用空格隔开。
st、ed、value取值均在32位有符号整数（int）的范围内，输入数据保证所有数据的value总和也在int范围内。

输出：

对应每个测试案例，输出小明可以获得的最大报酬

17	while(scanf("%d", &n) != EOF){

18	for(i=1; i<=n; i++){

19	scanf("%d %d %d", &p[i].st, &p[i].ed, &p[i].value);

20	dp[i] = 0;

21

}

22	sort(p+1, p+n+1, cmp);

23	dp[0] = 0;

24	for(i=1; i<=n; i++){

25	for(j=i-1; j>0; j--){

26	if(p[i].st >= p[j].ed)

27

break;

28

}

29	dp[i] = dp[j] + p[i].value;

30	if(dp[i] < dp[i-1])

31	dp[i] = dp[i-1];

32

}

33	printf("%d\n",dp[n]);

34

}

http://blog.csdn.net/wdy_yx/article/details/9833897
 在动态规划更新过程中，当考虑第 i 个项目时，我们需要比较加入第i 个项目 和不加第i个项目 所能产生价值的最大值。

       1. maxP[i-1]

        表示不加第i个项目，也就是前 i-1 个项目所能产生价值的最大值。这个比较好理解。

       2.maxP[preid]+ps[i].value

       当加入第i个项目后，之前项目中和第i个项目有重叠的项目肯定就不能做了，所以我们要查找前面不和第i 个项目重叠的前preid个项目 所能产生的最大价值。

       结束时间endt<= ps[i].begt的项目不和项目i重合，

1. struct PRO{  
2.     int begt;  
3.     int endt;  
4.     int val;  
5. public:  
6.     PRO(int begt_,int endt_,int val_):begt(begt_),endt(endt_),val(val_){};  
7.    
8. };  
9. std::vector<PRO> ps;  
10. int maxP[10001];  
11. int findpm(int b,int e,int t){  
12.     int id = b-1;//Attention  
13.     int mid;  
14.     while(b<=e){ //ATTENTION  <=  
15.         mid = (b+e)>>1;  
16.         if(ps[mid].endt<=t){  
17.             id = mid;  
18.             b = mid+1;  
19.         }else{  
20.             e = mid-1;  
21.         }  
22.     }  
23.     return id;  
24. }  
25.    
26. bool lessThan(const PRO& pl,const PRO& pr){  
27.     return pl.endt<pr.endt;  
28. }  
29. void init(int n){  
30.     ps.clear();  
31.     for(int i =0;i<=n;i++)  
32.         maxP[i]=0;  
33.    
34.     int bt;  
35.     int et;  
36.     int val;  
37.     ps.push_back(PRO(0,0,0)); //ATTENTION  
38.     for(int i = 0;i<n;i++){  
39.         scanf("%d %d %d",&bt,&et,&val);  
40.         ps.push_back(PRO(bt,et,val));  
41.     }  
42. }  
43. void getMax(int n){  
44.     std::sort(ps.begin(),ps.end(),lessThan);  
45.     for(int i = 1;i<n+1;i++){  
46.         int preid = findpm(0,i-1,ps[i].begt);  
47.         maxP[i] = std::max(maxP[i-1],maxP[preid]+ps[i].val);  
48.     }  
49.     printf("%d\n",maxP[n]);  
50. }  
51. void getMaxNew(int n){  
52.     std::sort(ps.begin(),ps.end(),lessThan);  
53.     int *dp = new int[ps.back().endt+1];  
54.     for(int i = 1;i<n+1;i++){  
55.         int temMax = std::max(dp[ps[i].endt],dp[ps[i].begt]+ps[i].val);  
56.         for(int j = ps[i].endt;j<ps.back().endt+1;j++)  
57.             dp[j] = temMax;  
58.     }  
59.     printf("%d\n",maxP[ps.back().endt]);  
60. } 

       ***********为什么动态规划变量为时间时会产生时间超长呢*************

       为什么time output limit,本题和 题目1463：招聘会，题目1434：今年暑假不AC 不同的地方在于1463、1434里面的时间为一天中的24小时，所以按照时间来动态规划的话，j的范围0<= j <=24，无论有多少个项目，dp的大小最大也为25。在本题中如果仍然按照时间来动态规划的话，j的maxT等于最晚的项目的结束时间，如果结束时间很晚的话，maxT很大，dp申请的空间也就很大，dp遍历所需时间也就长。

1. void getMaxNew(int n){  
2.     std::sort(ps.begin(),ps.end(),lessThan);  
3.     int maxT = ps.back().endt;  
4.     int *dp = new int[maxT+1];  
5.     memset(dp,0,(maxT+1)*sizeof(int));  
6.     for(int i = 1;i<n+1;i++){  
7.         int temMax = std::max(dp[ps[i].endt],dp[ps[i].begt]+ps[i].val);  
8.         for(int j = ps[i].endt;j<maxT+1;j++)  
9.             dp[j] = temMax;  
10.     }  
11.     printf("%d\n",dp[maxT]);  
12. }  

Read full article from 九度-1499-项目安排[解题代码] | Acm之家