POJ - 3616 Milking Time(DAG)

题目大意：给出N头牛的产奶时间段和产奶量，每接完一头牛的奶后，需要休息R分钟
问如何选择牛，才能使接到的产奶量达到最大

解题思路：DAG，按产奶的结束时间大小排序

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;

struct Interval{
    int start, end, val;
}inter[N];

int n, m, r;
int dp[N];

bool cmp(const Interval &a, const Interval &b) {
    return a.end < b.end;
}

void init() {
    for (int i = 0; i < n; i++)
        scanf("%d%d%d", &inter[i].start, &inter[i].end, &inter[i].val);
    sort(inter, inter + n, cmp);
}

void solve() {
    for (int i = 0; i < n; i++)
        dp[i] = inter[i].val;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (inter[i].start >= inter[j].end + r)
                dp[i] = max(dp[i], dp[j] + inter[i].val);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
}

int main() {
    while (scanf("%d%d%d", &m, &n, &r) != EOF) {
        init();
        solve();
    }
    return 0;
}