题目大意：一奶牛可以在一段时间内挤奶，挤完要休息一段时间。不同的时间段的量不一样。时间段不可以重叠，问做多能挤出多少奶？
Input
* Line 1: Three space-separated integers: N, M, and R
* Lines 2..M+1: Line i+1 describes FJ‘s ith milking interval withthree space-separated integers: starting_houri , ending_houri , and efficiencyi
Output
* Line 1: The maximum number of gallons of milk that Bessie can product in the N hours
Sample Input
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31
Sample Output
43
动态规划，先按开始时间排序。然后分别统计每一次能达到的最大值，在计算总的最大值
但一开始代码死活都通不过，最后通过的代码是这样
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 int dp[1024]; 7 8 struct Sche { 9 int s, e; 10 int v; 11 }; 12 13 int cmp2(Sche a, Sche b) 14 { 15 return a.s < b.s; 16 } 17 18 int cmp(const void *a, const void *b) { 19 Sche at = *(Sche *)a; 20 Sche bt = *(Sche *)b; 21 return at.s - bt.s; 22 } 23 24 Sche sche[1024]; 25 26 int main(int argc, char const *argv[]) 27 { 28 int n, m, r; 29 //freopen("input.txt","r",stdin); 30 scanf("%d %d %d",&n, &m, &r); 31 for(int i = 0; i < m; i++) { 32 scanf("%d %d %d",&sche[i].s, &sche[i].e, &sche[i].v); 33 sche[i].e += r; 34 } 35 qsort(sche, m, sizeof(sche[0]), cmp); 36 //sort(sche, sche + m, cmp2); 37 /*for (int i = 0; i < m; i++) 38 { 39 printf("%d %d %d\n", sche[i].s, sche[i].e, sche[i].v); 40 }*/ 41 for(int i = 0; i < m; i++) { 42 dp[i] = sche[i].v; 43 for(int j = 0; j < i; j++) { 44 if(sche[i].s >= sche[j].e) { 45 dp[i] = max(dp[i], dp[j] + sche[i].v); 46 } 47 } 48 } 49 int ans = dp[0]; 50 for(int i = 1; i < m; i++) { 51 ans = max(ans, dp[i]); 52 } 53 printf("%d\n",ans); 54 return 0; 55 }
通不过的原因是qsort的cmp函数一开始写的是 at.s < bt.s ,尝试了n次之后，改成at.s - bt.s才通过
原文：http://www.cnblogs.com/jasonJie/p/5830588.html