对比一下暴力和标程的区别，为何暴力还过不去？？

我的暴力想法就是排完序后肯定保证了左端点有序，这样可以直接枚举在区间范围内的时间段啊。（然后后续可以考虑优化成二分或者直接前缀和优化）

但是神奇的是我暴力调了1天没过，无奈考虑前缀和优化，竟然能过。

想问一下大佬，我的暴力思路出错了吗？还是实现？

暴力：

#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;
}
bool check(int x, int y)
{
	for (int i=x+1; i<y; i++)
		if (a[i].L>a[x].R) return 0; 
	
	return 1;
}
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 && check(j, i)) //这里改了
				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=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;
}