题目链接

Milking Time POJ - 3616

思路

$$ 首先按照开始时间排序，然后dp转移如下：\\\\dp[i] = c[i] + \max \limits_{1 \le j < i } dp[j] \left(if \quad b[j] + r \le a[i] \right) $$

时间复杂度

$$ O(M^2) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e6 + 10;

int a[MAXN], b[MAXN], c[MAXN];
int id[MAXN], dp[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int n, m, r;
    scanf("%d%d%d", &n, &m, &r);// don't forget &
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);// don't forget &
        id[i] = i;
    }
    sort(id + 1, id + 1 + m, cmp);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        int x = id[i];
        dp[i] = c[x];
        for (int j = 1; j < i; j++) {
            int y = id[j];
            if (b[y] + r <= a[x]) {
                dp[i] = max(dp[i], dp[j] + c[x]);
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d", ans);
    return 0;
}