我们从动态规划三要素角度分析这个问题：
| 项目 | 分析 |
|---|---|
| 状态 | $dp[i]$表示$i \sim n$时刻最长空暇时间 |
| 阶段 | 当前处理的时刻$i$ |
| 决策 | $\begin{equation} dp[i]\begin{cases} dp[i+1]+1(当前时刻无工作)\\ dp[i+worktime_{j}](当前时刻有工作) \end{cases} \end{equation}$ |
很明显，当前决策是基于该时刻后的时间段进行状态转移的，所以我们需要逆推时间。
这样划分子问题，正好满足了“子问题重叠性”、“无后效性”以及“最优子结构性”这三大条件。
再对边界以及目标进行分析：
| 项目 | 分析 |
|---|---|
| 边界 | $dp[n]=0$，即最后一刻无空闲 |
| 目标 | $dp[1]$，即$1 \sim n$时刻的空闲时间 |
最后给出参考代码：
#include <bits/stdc++.h>
#define MAXN 10001
using namespace std;
int n,k;
pair<int,int> work[MAXN];
int num;
int dp[MAXN];
int cur[MAXN];
bool cmp(const pair<int,int> a, const pair<int,int> b) {
return a.first > b.first;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for ( int i = 1; i <= k; ++i ) {
cin >> work[i].first >> work[i].second;
++cur[work[i].first];
}
sort( work + 1, work + 1 + k, cmp );
for ( int i = n; i >= 1; --i ) {
if ( cur[i] == 0 ) {
dp[i] = dp[i + 1] + 1;
} else
for ( int j = 1; j <= cur[i]; ++j ) {
++num;
dp[i] = max(dp[i], dp[i + work[num].second]);
}
}
cout << dp[1] << endl;
return 0;
}