POJ 3616 Milking Time——区间DP

POJ 3616 Milking Time——区间DP

一共有M个区间，我们可以对这M个区间进行dp，定义dp[i]为遍历前i - 1个区间得到的最大产奶量(要保证【第i个区间的开始时间】小于【从前i-1个区间选出的一个区间的结束时间】),注意要先对区间的时间进行排序，还要注意dp[M]并不一定是结果，因为可能根本达不到dp[M],最后要对所有dp值遍历一便找最大值

#include #include #include #include using namespace std;const int maxn = 1000000 + 10;int dp[maxn];struct Time { int left, right, val; bool operator < (const Time &another) const { if (left != another.left) return left < another.left; else return right < another.right; }}time[maxn];int main(){ int N, M, R; scanf("%d %d %d", &N, &M, &R); for (int i = 1; i <= M; i++) { scanf("%d %d %d", &time[i].left, &time[i].right, &time[i].val); time[i].right += R; } sort(time + 1, time + 1 + M); for (int i = 1; i <= M; i++) { dp[i] = time[i].val; for (int j = 1; j < i; j++) { if (time[j].right <= time[i].left) { dp[i] = max(dp[i], dp[j] + time[i].val); } } } int ans = -1; for (int i = 1; i <= M; i++) ans = max(dp[i], ans); cout << ans << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。