額……這道題貌似也不怎么強(qiáng)大，但是著實(shí)讓我糾結(jié)，所以我又開始求助了，然后求助成功，解題，然后貼上來，以免以后忘記……
題目大意是這樣的，給一段時(shí)間N，給M個(gè)時(shí)間段，給開始時(shí)間和結(jié)束時(shí)間，每個(gè)時(shí)間段有一個(gè)效率，每次用完某一時(shí)間段的效率必須休息R小時(shí)，求最高的效率。
好吧，存儲(chǔ)結(jié)構(gòu)沒有異議，一個(gè)量，三個(gè)參數(shù)，果斷的結(jié)構(gòu)體存儲(chǔ)啊，方便得體，多好啊……
剛 開始我果斷的打算把它當(dāng)成一個(gè)01背包來做，但是果斷的錯(cuò)了，被我自己否決了（還好沒寫……）我的想法是直接把每一段的結(jié)束時(shí)間減去開始時(shí)間，然后成為一個(gè)消耗時(shí)間段，然后抽象……N代表背包總?cè)萘浚琈代表物品個(gè)數(shù)，消耗時(shí)間段代表著物品占用的空間，效率就是物品價(jià)值，一個(gè)華麗麗的01背包解決……當(dāng)然這 個(gè)錯(cuò)了，原因是既然給了每個(gè)時(shí)間段的開始時(shí)間和結(jié)束時(shí)間，還有休息時(shí)間，那如果重疊了怎么算……然后就果斷的否決了。
實(shí)際上正確的狀態(tài)是當(dāng) 選用第i個(gè)時(shí)間段為結(jié)尾的時(shí)候，所獲得的最大效率，當(dāng)然得把時(shí)間段的先后先排個(gè)序，按照開始時(shí)刻排序，這樣比較有愛……這樣的話當(dāng)處理第i個(gè)時(shí)間段也就是 f[i]的時(shí)候，之前需要計(jì)算的都在第i段的前面。當(dāng)處理到第i段的時(shí)候，前面必然有一個(gè)j，使得以j為結(jié)尾的時(shí)候，所得效率最大，從而保證到第j段的最 大效率加上第i段的效率最大，j可以是i前面的任意一段時(shí)間，反正保證了最大就行。初始化的時(shí)候要有這么一句：f[i]=in[i].ef，這樣就是防止 有前面所有段全都不用這種情況。方程是這樣的：f[i]=max(f[j]+in[i].ef，f[i])，in[i].ef是第i段時(shí)間中的效率。
但是一定要注意一點(diǎn)，選用的時(shí)間區(qū)間除了端點(diǎn)以外是不能重合的，還得記得把休息時(shí)間加上……
特別鳴謝：翔哥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;
}