1. 题目

传送门＝￣ω￣＝

2. 题解

考虑倒推。
设 $f(i)$为时刻 $i$到时刻 $n$之间的最大空暇时间。
如果时刻 $i$无任务开始，显然 $f(i)=f(i+1)+1$。
否则枚举开始于时刻 $i$的任务，设当前枚举的任务结束时间为 $j$，则 $f(i)=max(f(j+1))$。
至于保存每个时刻有哪些任务开始，用链表（或者模拟，即链式前向星）即可。

还有一点要注意的，一个任务开始与 $a$，持续时间为 $b$，那么它的结束时间不是 $a+b$而是 $a+b-1$。
下面的代码中我直接用 $a+b$表示任务结束时间，这样在算 $f(i)=max(f(j+1))$时就不用加一了。

代码：

#include <bits/stdc++.h>
using namespace std;
static const int ms=10005;
int n,k,t[ms],nxt[ms],head[ms],ls,f[ms];
void addt(int a,int b){t[ls]=b,nxt[ls]=head[a],head[a]=ls++;}
int main()
{
    scanf("%d%d",&n,&k),memset(head,-1,sizeof(head));
    for(int i=1,a,b;i<=k;i++)scanf("%d%d",&a,&b),addt(a,a+b);
    for(int i=n;i>=1;i--)
        if(head[i]==-1)f[i]=f[i+1]+1;
        else for(int j=head[i];j!=-1;j=nxt[j])f[i]=max(f[i],f[t[j]]);
    printf("%d\n",f[1]);
    return 0;
}