首页 > 代码库 > POJ 3616 Milking Time 挤奶问题，带权区间DP

POJ 3616 Milking Time 挤奶问题，带权区间DP

2024-07-27 20:34:45   220人阅读

题目链接：POJ 3616 Milking Time

Milking Time
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4837 Accepted: 2034

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

Source

USACO 2007 November Silver

题意：

每一个挤奶区间都有一个效率，奶牛每挤完依次奶需要休息R小时，问怎样安排才能使效率最高。

分析：

如果没有效率问题，那么按照结束时间递增排序总是最优的，这样可以覆盖到尽可能多的区间，当加上效率时，我们要考虑到前面的时间获得的效率是否比当前时间段的效率要更高。若以dp[k]表示第k个区间的效率（注意已经排好序，因而就是第k个结束时间的效率。则状态转移方程为：

dp[k] = max(dp[k], dp[j]+itv[j].ef);

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1000010;
const int MAX_M = 1010;

struct ITV {
    int st, ed, ef;
    bool operator < (const ITV& b) const {
        if(ed == b.ed) return st < b.st;
        return ed < b.ed;
    }
}itv[MAX_M];
int N, M, R, dp[MAX_M];

void solve() {
    sort(itv, itv+M);
    for(int i = 0; i < M; i++) dp[i] = itv[i].ef;
    int res = 0;
    for(int i = 0; i < M; i++)
        for(int j = 0; j < i; j++)
            if(itv[i].st - itv[j].ed >= R) {
                dp[i] = max(dp[i], dp[j]+itv[i].ef);
                if(dp[i] > res) res = dp[i];
            }
   printf("%d\n", res);
}

int main() {
    while(~scanf("%d%d%d", &N, &M, &R)) {
        for(int i = 0; i < M; i++)
            scanf("%d%d%d", &itv[i].st, &itv[i].ed, &itv[i].ef);
        solve();
    }
    return 0;
}

POJ 3616 Milking Time 挤奶问题，带权区间DP


联系
我们