全WA

#include<bits/stdc++.h>
using namespace std;
const int M=1e4+5;
struct node{
	int p,t;
}work[M];
int dp[M];
vector<int> cnt[M];
int main(){
	int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&work[i].p,&work[i].t),cnt[work[i].p+work[i].t-1].push_back(i);
	for(int i=1;i<=n;i++){
		if(!cnt[i].size())dp[i]=dp[i-1]+1;
		else{
			for(int j=0;j<cnt[i].size();j++){
				dp[i]=max(dp[work[cnt[i][j]].p-1],dp[i]);
			}
		}
	}
	printf("%d",dp[n]);
	return 0;
}

AC（倒序）

#include<bits/stdc++.h>
using namespace std;
const int M=1e4+5;
struct node{
	int p,t;
}work[M];
int dp[M];
vector<int> cnt[M];
int main(){
	int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&work[i].p,&work[i].t),cnt[work[i].p].push_back(i);
	for(int i=n;i>=1;i--){
		if(!cnt[i].size())dp[i]=dp[i+1]+1;
		else{
			for(int j=0;j<cnt[i].size();j++){
				dp[i]=max(dp[work[cnt[i][j]].t+i],dp[i]);
			}
		}
	}
	printf("%d",dp[1]);
	return 0;
}