首页 > 代码库 > poj 3616

poj 3616

2024-08-11 16:06:38   222人阅读

题目大意：一奶牛可以在一段时间内挤奶，挤完要休息一段时间。不同的时间段的量不一样。时间段不可以重叠，问做多能挤出多少奶？

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 21 2 810 12 193 6 247 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才通过

poj 3616


联系
我们