P1280 尼克的任务（DP）

注意要倒序。

设f[i]表示从第i时刻到第n时刻的最大休闲时间。

```cpp

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int N=10005;
int f[N];
int cnt[N];
vector<int> v[N]; 
int n,k;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++){
		int p,t;
		scanf("%d%d",&p,&t);
		v[p].push_back(t);
		cnt[p]++;
	}
	for(int i=n;i>=1;i--){
		if(cnt[i]){
			for(int j=0;j<cnt[i];j++){
				f[i]=max(f[i],f[i+v[i][j]]);
			}
		}
		else f[i]=f[i+1]+1;
	}
	printf("%d",f[1]);
	return 0;
}

```