典型的给出区间任务和效益值，然后求最大效益值的任务取法。

属于一维DP了。

一维table记录的数据含义：到当前任务的截止时间前的最大效益值是多少。

注意， 这表示当前任务一定要选择，但是最终结果是不一定选择最后一个任务，故此最后需要遍历找到table数组的最大值，当然计算过程中使用一个数记录最终最大值也是可以的。

状态转移方程就是： tbl[i] = MAX({from tbl[0]->tbl[i-1] }+ weight[i] )，即区间0到i-1加上i的当前效益值。

#include 
  
   
#include 
   
     #include 
    
      using std::sort; const int MAX_M = 1001; const int MAX_N = 1000001; int N, M, R; struct Interval { int sta, end, effi; bool operator<(const Interval &i) const { return end < i.end; } }; Interval inter[MAX_M]; long long tbl[MAX_M]; inline long long max(long long a, long long b) { return a > b ? a : b; } long long getMaxEffi() { if (M < 1) return 0LL; long long maxEffi = 0; sort(inter, inter+M); for (int i = 0; i < M; i++) { tbl[i] = inter[i].effi; for (int j = 0; j < i; j++) { if (inter[j].end <= inter[i].sta) tbl[i] = max(tbl[i], tbl[j]+inter[i].effi); } maxEffi = max(maxEffi, tbl[i]); } return maxEffi; } int main() { while (scanf("%d %d %d", &N, &M, &R) != EOF) { for (int i = 0; i < M; i++) { scanf("%d %d %d", &inter[i].sta, &inter[i].end, &inter[i].effi); inter[i].end += R; } printf("%lld\n", getMaxEffi()); } return 0; }