POJ3616 Milking Time

题目大意

奶牛Bessie非常的勤奋，她想在N时间内产出最多的牛奶。我们的老朋友Farmer John 有M个挤奶的时间段，有可能有重叠。每个时间段由开始时间和结束时间组成，每个时间段Bessie会产出e的奶，Farmer John可以在这些时间段里为Bessie挤奶，需要注意的是，必须要挤够一个完整的时间段。但是我们的Bessie也会劳累，每挤完一次奶，她就要休息R小时，求在N小时内挤出奶的最大量

思路

DP，d[i] 表示在i这个时刻，挤出奶的最大量。时间段表示为a[j] a[j].x为开始时间 a[j].y 为结束时间 a[j].e就是产奶量。我们需要将a[i] 以结束时间从小到大排序。
状态转移方程表示为：
如果a[j].y == i
d[i] = max(d[i], d[i-1], d[a[j].x - R] + a[j].e)
否则
d[i] = d[i-1]
具体意思是，如果当前的挤奶时间段a[j]的结束时间刚好等于i， 那么d[i] 的值就有三种可能，一种保持不变，一种不在a[j]时间段挤奶，那么d[i]的值就等于上一个小时的值，另一种就是在a[j]时间段挤奶，那么我们需要加上a[j].x - R 时刻的最大奶量 和 a[j].e，在这三者中找个最大的就行。选用a[j].y是因为保证了无后效性。

代码

#include 
#include 
#include 
using namespace std;long long d[1000020]<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！