額……這道題貌似也不怎么強大，但是著實讓我糾結，所以我又開始求助了，然后求助成功，解題，然后貼上來，以免以后忘記……
題目大意是這樣的，給一段時間N，給M個時間段，給開始時間和結束時間，每個時間段有一個效率，每次用完某一時間段的效率必須休息R小時，求最高的效率。
好吧，存儲結構沒有異議，一個量，三個參數，果斷的結構體存儲啊，方便得體，多好啊……
剛 開始我果斷的打算把它當成一個01背包來做，但是果斷的錯了，被我自己否決了（還好沒寫……）我的想法是直接把每一段的結束時間減去開始時間，然后成為一個消耗時間段，然后抽象……N代表背包總容量，M代表物品個數，消耗時間段代表著物品占用的空間，效率就是物品價值，一個華麗麗的01背包解決……當然這 個錯了，原因是既然給了每個時間段的開始時間和結束時間，還有休息時間，那如果重疊了怎么算……然后就果斷的否決了。
實際上正確的狀態是當 選用第i個時間段為結尾的時候，所獲得的最大效率，當然得把時間段的先后先排個序，按照開始時刻排序，這樣比較有愛……這樣的話當處理第i個時間段也就是 f[i]的時候，之前需要計算的都在第i段的前面。當處理到第i段的時候，前面必然有一個j，使得以j為結尾的時候，所得效率最大，從而保證到第j段的最 大效率加上第i段的效率最大，j可以是i前面的任意一段時間，反正保證了最大就行。初始化的時候要有這么一句：f[i]=in[i].ef，這樣就是防止 有前面所有段全都不用這種情況。方程是這樣的：f[i]=max(f[j]+in[i].ef，f[i])，in[i].ef是第i段時間中的效率。
但是一定要注意一點，選用的時間區間除了端點以外是不能重合的，還得記得把休息時間加上……
特別鳴謝：翔哥zzxyyx_1
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct interval
{
long st, en, ef;
}in[1001];
long max(long a, long b)
{
if (a > b) return a;
else return b;
}
long cmp(interval a, interval b)
{
return a.st < b.st;
}
int main()
{
long n, m, r, i, j, f[1001], maxi;
cin >> n >> m >> r;
for (i = 1; i <= m; i++)
{
scanf("%ld%ld%ld", &in[i].st, &in[i].en, &in[i].ef);
}
sort(in + 1, in + 1 + m, cmp);
for (i = 1; i <= m; i++) f[i] = in[i].ef;
for (i = 2; i <= m; i++)
for (j = 1; j < i; j++)
{
if (in[j].en + r <= in[i].st)
{
f[i] = max(f[j] + in[i].ef, f[i]);
}
}
for (i = 1; i <= m; i++)
if (f[i] > maxi) maxi = f[i];
cout << maxi << endl;
return 0;
}