closefrom

这题显然是一个线性动规，那么肯定是第一时间想到设f[i]:1_{i的最大空闲时间，但是，想了一下之后发现，第i时刻的最大空闲时间是和后面i+选择任务的持续时间的时刻有关系的，那么，正着找肯定是不行的，我们来试一下倒着搜,即设f[i]表示i}n的最大空闲时间，经尝试，发现是完全可行的，可以列出动态转移方程如下

（本时刻无任务）f[i]=f[i+1]+1;//继承上一个时刻的最大空闲时间后+1

（本时刻有任务）f[i]=max(f[i],f[i+a[sum])//a[sum]表示在这个时刻的任务的持续时间，找出选择哪一个本时刻任务使空闲时间最大化

那么既然是倒着搜，从后往前的任务对应的开始时间自然也要反过来，从大到小排序（同时也是为了把相同开始时间的任务放到一起）,当然在进行状态刷新的时候别忘了拿sum不断计一下已经到哪一个任务了

#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,f[10005],sum[10005],ls=1;
struct node{
    int p,t;
}nk[10005];
bool cp(node a,node b){return a.p>b.p;}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d",&nk[i].p,&nk[i].t);
        sum[nk[i].p]++;
    }
    sort(nk+1,nk+k+1,cp);
    for(int i=n;i>=1;i--){
        if(sum[i]==0)f[i]=f[i+1]+1;
        else for(int j=1;j<=sum[i];j++){
            if(f[i+nk[ls].t]>f[i])f[i]=f[i+nk[ls].t];
            ls++;
        }
    }
    printf("%d",f[1]);
    return 0;
}