这道题我一直按照往常的思路想
f[i]为前i个任务的最大空暇时间
然后想不出来怎么做……
后来看了题解
发现这里设的状态是时间，不是任务
自己思维还是太局限了，题做得太少。
很多网上题解都反着做，那么麻烦干嘛
设f[i]为前i时间内的最大空暇时间。
这里是更新后来的状态，和以前不一样。
如果i为某个任务的开始时间，则
f[i+t-1] = max(f[i+t-1], f[i])
也就是继承过去，取max
如果不是的话
f[i] = max(f[i], f[i-1] + 1)
加上获得的空暇时间
最后输出f[time],time为总时间
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 11234;
int f[MAXN], time, n;
struct node
{int l, r;bool operator < (const node& rhs) const{return l < rhs.l || (l == rhs.l && r < rhs.r); }
}a[MAXN];int main()
{scanf("%d%d", &time, &n);REP(i, 1, n + 1) scanf("%d%d", &a[i].l, &a[i].r);sort(a + 1, a + n + 1);memset(f, -63, sizeof(f));f[0] = 0;int p = 1;REP(i, 1, time + 1){if(a[p].l == i){while(a[p].l == i)f[i + a[p].r - 1] = max(f[i + a[p].r - 1], f[i-1]), p++;}else f[i] = max(f[i], f[i-1] + 1);}printf("%d\n", f[time]);return 0;
}后来做到洛谷P1280，竟然做不出来了，看来对题解还是没有深刻的理解
（1）初始化问题。本来以为全部都是0无所谓的，然后就WA。
因为求最大，所以初始化为最小，同时f[0] = 0
（2）这里推时间是从f[i-1]推，不是f[i]
然后我发现把这个f数组输出来乱七八糟的。
但是答案是对的
有点迷（因为下标是时间？？）
最后，这11天过来我的代码风格还是有少许改变的
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 112345;
int f[MAXN], n, k;
struct node
{ int l, r;void read() { scanf("%d%d", &l, &r); r = l + r - 1; }bool operator < (const node& rhs) const{return l < rhs.l || (l == rhs.l && r < rhs.r);}
}a[MAXN];int main()
{scanf("%d%d", &n, &k);REP(i, 0, k) a[i].read();sort(a, a + k);memset(f, -63, sizeof(f));f[0] = 0;int p = 0;_for(i, 1, n){if(a[p].l == i){while(a[p].l == i) f[a[p].r] = max(f[a[p].r], f[i-1]), p++;}else f[i] = max(f[i], f[i-1] + 1);}printf("%d\n", f[n]);return 0;
}