POJ 3616 Milking Time DP（带权重的区间动态规划）

本文主要是介绍POJ 3616 Milking Time DP（带权重的区间动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0…N-1) so that she produces as much milk as possible.
Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_houri ≤ N), an ending hour (starting_houri < ending_houri ≤ N), and a corresponding efficiency (1 ≤ efficiencyi ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.
Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.
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

题目大意：
奶牛有m次挤奶区间，每次挤奶后要休息r时间，休息完毕后可以立即继续挤奶，每个挤奶区间的产量不尽相同，求出在给定时间范围内可获得的最大产量。
解题思路：
该题是带权重的任务调度问题，回想之前的无权重区间调度，我们是使用贪心算法，每次都选择最早结束的区间。
对于该题，可使用动态规划，动态规划方程为

tmp是与区间i兼容的、具有最大下标的区间
//不选区间i 为dp[i-1]
//选择区间i 为dp[tmp] + list[i].v
dp[i] = max(dp[i - 1], dp[tmp] + list[i].v);

AC代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int dp[1001];//dp[i]表示考虑到第i个任务的结果
#define INF 0x3fffffff
struct node {int s, e, v;
}list[1001];
bool cmp(node a, node b) { return a.e < b.e; }//按照结束时间排序
int main() {int n, m, r;while (scanf("%d%d%d", &n, &m, &r)!=EOF) {for (int i = 1; i <= m; i++) {scanf("%d%d%d", &list[i].s, &list[i].e, &list[i].v);}sort(list + 1, list + 1 + m, cmp);dp[0] = 0;//初始化for (int i = 1; i <= m; i++) {int tmp = i -1;//tmp是与区间i兼容的、具有最大下标的区间while (tmp>0 && list[tmp].e + r > list[i].s) tmp--;dp[i] = max(dp[i - 1], dp[tmp] + list[i].v);}cout << dp[m] << endl;}
}