动态规划

设计 $dp_i$ 为第 $i$ 分钟空闲或恰好开始工作的情况下 $[i,n]$ 中最多包含的空闲时刻数量。

预处理得到不早于时刻 $i$ 开始的工作中，开始最早的工作的开始时刻（可能有多个工作符合要求，但时刻只有一个）记为 $nxt_i$ 后从 $n$ 向 $1$ 倒序转移。

记 $v_i$ 为在时刻 $i$ 开始的工作的结束时刻形成的集合，写出状态转移方程。

• 若 $i = nxt_i$，那么 $dp_{i} = \max\limits_{j \in v_i}(dp_{j+1})$
• 若 $i \neq nxt_i$，那么 $dp_{i} = dp_{nxt_i} + (nxt_i - i)$。

动态规划结束后 $dp_1$ 即为答案。

由于 $n,k$ 同阶，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,k,nxt,dp[10'005];
vector<int> v[10'005];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++){
        static int l,r;
        scanf("%d%d",&l,&r);
        r=l+r-1;
        v[l].push_back(r);
    }
    nxt=n+1;
    for(int i=n;i>=1;i--){
        if(v[i].empty()) dp[i]=dp[nxt]+(nxt-i);
        else{
            for(int j:v[i]) dp[i]=max(dp[i],dp[j+1]);
            nxt=i;
        }
    }
    printf("%d\n",dp[1]);
    return 0;
}