给你ｎ个区间，每个区间对应一个生产值，让你选出其中的某些区间，使得这些区间中，所选的任意两个相邻区间相差至少为ｒ，并且这些区间的生产值和最大．

将区间按端点排序下，先按区间左端点从小到大排，相同则按右端点从小到大排．

dp[i] 为前ｉ个区间中所得最大值，就类似与最长递增子序列问题中，搞搞就好了．

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1005;
struct node {
    int s, e, f;
    bool operator < (const node & op) const {
        return s < op.s || s == op.s && e < op.e;
    }
} e[M];
int dp[M];
int main()
{
    int n, m, r;
    scanf("%d %d %d", &n, &m, &r);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &e[i].s, &e[i].e, &e[i].f);
    }
    sort(e + 1, e + m + 1);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        dp[i] = e[i].f;
        for (int j = 1; j < i; j++) {
            if (e[j].s - e[i].e >= r || e[i].s - e[j].e >= r) {
                if (dp[i] < dp[j] + e[i].f) {
                    dp[i] = dp[j] + e[i].f;
                }
            }
        }
        ans = max(dp[i], ans);
    }
    printf("%d\n", ans);
    return 0;
}