标程：

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;

struct node
{
	int L, R;
}a[N];
int n, k, f[N], ans=0, s[N];
bool cmp(node a, node b)
{
	return a.L<b.L;
}
int main()
{
	for (int i=0; i<=10000; i++) f[i]=-1e9;
	
	scanf("%d%d", &n, &k);
	for (int i=1; i<=k; i++)
	{
		scanf("%d%d", &a[i].L, &a[i].R);
		a[i].R+=a[i].L-1;
		s[a[i].L]++;
	}
	sort(a+1, a+1+k, cmp);
	
	for (int i=1; i<=n; i++) s[i]+=s[i-1];
	for (int i=1; i<=k; i++) if (s[a[i].L-1]==0) f[i]=a[i].L-1;
	
	for (int i=1; i<=k; i++)
		for (int j=1; j<i; j++)
			if (a[j].R<a[i].L && s[a[i].L-1]-s[a[j].R+1-1]==0)
				f[i]=max(f[i], f[j]+a[i].L-a[j].R-1);
	
	for (int i=1; i<=k; i++) if (a[i].R>=a[k].L) ans=max(ans, f[i]+n-a[i].R);
	printf("%d", ans);
	return 0;
}

小优化：

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;

struct node
{
	int L, R;
}a[N];
int n, k, f[N], ans=0, s[N];
bool cmp(node a, node b)
{
	return a.L<b.L;
}
int main()
{
	for (int i=0; i<=10000; i++) f[i]=-1e9;
	
	scanf("%d%d", &n, &k);
	for (int i=1; i<=k; i++)
	{
		scanf("%d%d", &a[i].L, &a[i].R);
		a[i].R+=a[i].L-1;
		s[a[i].L]++;
	}
	sort(a+1, a+1+k, cmp);
	
	for (int i=1; i<=n; i++) s[i]+=s[i-1];
	for (int i=1; i<=k; i++) if (s[a[i].L-1]==0) f[i]=a[i].L-1;
	
	for (int i=1; i<=k; i++)
		for (int j=i-1; j>=1; j--)
		{
			if (a[j].R>=a[i].L) continue;
			
			if (s[a[i].L-1]-s[a[j].R+1-1]==0) f[i]=max(f[i], f[j]+a[i].L-a[j].R-1);
			else break;
		}
				
	
	for (int i=1; i<=k; i++) if (a[i].R>=a[k].L) ans=max(ans, f[i]+n-a[i].R);
	
//	for (int i=1; i<=k; i++) printf("%d:%d   ", i, f[i]);
	printf("%d", ans);
	return 0;
}

因为排过序了，如果 $j$ 不满足，也就是 $[i, j]$ 区间内有任务开始，那么 $k$ 肯定也不满足（$j \ge k$）

所以如果不满足直接 break 不行吗？