额……这道题貌似也不怎么强大，但是着实让我纠结，所以我又开始求助了，然后求助成功，解题，然后贴上来，以免以后忘记……
题目大意是这样的，给一段时间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;
}