P1069 闲时自可期 官方题解

【部分分：测试点 1∼41\sim 41∼4】

• 当 $n,k\leq20$ 时，可以枚举记录员每次空闲且收到任务时选择哪一项任务。确定选择后，忙碌期间开始的任务全部跳过，再继续处理下一次空闲时刻。
• 每个任务至多产生一次选择，直接枚举的复杂度为指数级。检查一组选择需要 $\mathcal O(n+k)$ 的时间。
• 这个做法保留了题目中的强制选择规则。重复计算来自相同的“重新空闲时刻”，因此后续只需要保存这些时刻的最优答案。

【部分分：测试点 5∼85\sim 85∼8】

• 有任务开始的时刻不超过 $20$ 个，并且每个时刻至多有两项任务。我们把任务按照开始时刻排序，递归处理记录员下一次空闲后遇到的第一个事件时刻。
• 忙碌期间的事件不产生分支。只有空闲时同时出现两项任务时，递归才分成两支，因此分支层数不超过 $20$。
• 时间复杂度为 $\mathcal O(2^{20}+k\log k)$。这说明真正有用的状态是“从某个时刻重新开始安排”，而不是已经选择过哪些任务。

【部分分：测试点 9∼129\sim 129∼12】

• 定义 $f_i$ 表示第 $i$ 分钟开始时记录员空闲，从第 $i$ 分钟到工作日结束最多能够得到多少分钟闲时。边界为 $f_{n+1}=0$。
• 若第 $i$ 分钟没有任务开始，这一分钟一定是闲时，所以 $f_i=f_{i+1}+1$。否则必须选择一项从第 $i$ 分钟开始的任务，于是

• 直接对每个 $i$ 扫描全部任务即可实现，时间复杂度为 $\mathcal O(nk)$，空间复杂度为 $\mathcal O(n)$。

【部分分：测试点 13∼1513\sim 1513∼15】

• 特殊性质保证每项任务结束后立刻到达另一个事件时刻，或者已经到达第 $n+1$ 分钟。因此任务转移的端点都在事件集合中。
• 将全部开始时刻与 $n+1$ 排序，只在这些时刻保存 $f$。两个相邻事件之间没有任务开始，其中每一分钟都直接贡献闲时。
• 对每项任务只做一次转移，排序后时间复杂度为 $\mathcal O(k\log k)$，空间复杂度为 $\mathcal O(k)$。完整数据只需要进一步消去事件压缩的限制。

【正解】

• 考虑记录员在第 $i$ 分钟开始时恰好空闲。此前没有处理的任务已经交给其他人，此后也不会重新出现，所以过去做过哪些选择已经不再重要。

• 从这一刻开始，后续安排只由当前时刻 $i$ 决定。定义 $f_i$ 表示第 $i$ 分钟开始时记录员空闲，从第 $i$ 分钟至工作日结束最多能够得到的闲时。

• 第 $n+1$ 分钟已经越过工作日，不再产生闲时，因此边界为 $f_{n+1}=0$。

• 记 $J_i$ 为所有在第 $i$ 分钟开始的任务。若 $J_i$ 为空，这一分钟必然成为闲时，下一分钟仍然空闲，所以 $f_i=f_{i+1}+1$。

• 若 $J_i$ 非空，题目要求必须选择其中一项。选择持续 $t$ 分钟的任务后，这 $t$ 分钟都不会产生闲时，并在第 $i+t$ 分钟重新空闲。

• 因而完整转移为

• 转移只会从 $f_i$ 访问下标更大的状态，所以按照 $i=n,n-1,\ldots,1$ 的顺序计算即可。
• 预先把每项任务的持续时间放入对应的 $J_{p_i}$。每一分钟只处理一次，每项任务也只会在计算其开始时刻时被枚举一次。
• 答案为 $f_1$。时间复杂度为 $\mathcal O(n+k)$，空间复杂度为 $\mathcal O(n+k)$。多组数据之间需要清空本组使用过的 $J_i$，并重新设置 $f_{n+1}=0$。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/194Name:rest.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#include <algorithm>11#define MAXN 20001012using namespace std;13 14int c,T,n,k,Dp[MAXN];15vector <int> Job[MAXN];16 17void Solve() {18    scanf("%d%d",&n,&k);19    int In1,In2;20    for (int i=1;i<=k;i++) {21        scanf("%d%d",&In1,&In2);22        Job[In1].push_back(In2);23    }24    Dp[n+1]=0;25    for (int i=n;i>=1;i--) {26        if (Job[i].empty()) Dp[i]=Dp[i+1]+1;27        else {28            Dp[i]=0;29            for (int j=0;j<(int)Job[i].size();j++) {30                Dp[i]=max(Dp[i],Dp[i+Job[i][j]]);31            }32        }33    }34    printf("%d\n",Dp[1]);35    for (int i=1;i<=n;i++) Job[i].clear();36    return;37}38 39int main() {40    scanf("%d%d",&c,&T);41    while (T-->0) Solve();42    return 0;43}