Luogu1280 尼克的任务

不看题解真的不会做

(f[i])表示最大空闲时间

但是要逆推

方程

(if(b[i]==0)ans[i]=ans[i+1]+1;)

(if(ans[i+a[q].t]>ans[i])ans[i]=ans[i+a[q].t];)

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll mx=10010;

ll n, k, q=1;
ll b[mx], ans[mx];
struct node{ll p, t;}a[mx];

bool cmp(node a, node b) { return a.p>b.p; }
int main(){
    scanf("%lld %lld", &n, &k);
    for(ll i=1; i<=k; i++)
        scanf("%lld %lld", &a[i].p, &a[i].t), b[a[i].p]++;
    sort(a+1, a+k+1, cmp);
    for(ll i=n; i>0; i--){
        if(b[i]==0) ans[i]=ans[i+1]+1;
        else{
            for(ll j=1; j<=b[i]; j++){
                if(ans[i+a[q].t]>ans[i])ans[i]=ans[i+a[q].t];
                q++;
            }
        }
    }

    printf("%lld", ans[1]);
    return 0;
}