太阳照常升起，总有人不被选中

城里有一条很长的街。

街上住着十万人。每个人站出来，都能给庆典贡献一点热闹。有人敲锣，价值一块。有人喷火，价值十亿。财政大臣看了一眼名单，做出了非常成熟的决定：全要。

消防大臣说不行。

庆典有一条规定。连续出门的人不能超过 k 个。否则整条街都去广场了，家里没人看火。至于为什么庆典期间家里一定会着火，这是王国的底层设定，不讨论。

财政大臣开始做表。

走到第 i 户。前面已经连续出门 0 个、1 个、2 个……一直到 k 个。每种情况记一个最大热闹值。

表很宽。

街也很长。

十万人乘十万人。庆典还没开始，财政部先结束了。

这时，门口负责锁门的大爷问了一句：

“为什么一直数出去的人？”

“规定写的就是出去的人。”

“那你把留下的人画出来。”

留下的人很少。或者很多。都没关系。

只要相邻两个留下的人之间，最多夹着 k 个出门的人，规定就没有被违反。换句话说，两个留下的人，门牌号之差不能超过 k+1。

财政大臣突然不需要管理所有热闹了。

他只需要安排沉默。

总得有人不被选中。

然后让损失尽量小。

这条街叫 P2034。

简化题面

┌─ [P2034] 选择数字
├─ 平台: 洛谷
├─ 题意: 给定 n 个非负整数，选择其中一些，使选中数之和最大。
├─ 输入: 第一行 n、k；接下来 n 行，每行一个整数 a_i。
├─ 输出: 可行选择的最大总和。
├─ 数据范围: 1 <= n <= 10^5，1 <= k <= n，0 <= a_i <= 10^9。
├─ 关键限制: 连续被选择的位置不能形成长度超过 k 的连续段。
└─ 完整题面: https://www.luogu.com.cn/problem/P2034

题面说连续，我们偏要找断点

P2034 给出 n 个数，要选出其中一些，使选中数字的和最大。同时，不能连续选择超过 k 个位置。

最顺手的状态，是记录“当前位置连续选了多少个”。

它也最忠于题面。

忠得有点过头。

n 和 k 都可能很大。把连续长度直接放进状态，状态数会变成 O(nk)。题面说一句“连续”，我们就背着整个 k 往前走。像一个人出门买葱，顺便把厨房扛上。

这道题真正的转折，不是想起单调队列。

是换了被记录的对象。

设所有数字的总和为 S。选中和最大，等价于舍弃和最小：

最大选中和 = S - 最小舍弃和

现在看两个相邻的舍弃位置 j 和 i。

它们之间连续选中了 i-j-1 个数。合法条件是：

i - j - 1 <= k
i - j <= k + 1

“连续选中不能超过 k 个”，被翻译成了“相邻舍弃点距离不能超过 k+1”。

连续长度没了。

只剩两个点之间的距离。

状态不是题面的复读机

定义：

dp[i] = 位置 i 不选时，前 i 个位置的最小舍弃和

如果这次在 i 停下，上一个舍弃点 j 不能离得太远：

max(0, i-k-1) <= j <= i-1

于是：

dp[i] = a[i] + min(dp[j])

到这里，单调队列才获得出场许可。

不是因为题目在“单调队列”章节。不是因为看到 k 就条件反射地掏 deque。是因为 DP 每次都在一个向右滑动的固定窗口里查询最小值。

因果顺序很重要：

连续约束
-> 找到打断连续段的位置
-> 最小化打断的代价
-> 前驱落进固定窗口
-> 维护窗口最小值
-> 单调队列

这是一步一步推理得出的。思考链很重要。单调队列是标签，但只是一小步。

队列里都是暂时还有未来的人

deque 保存候选位置，队头是当前窗口中 dp 最小的位置。

假设队列里已经有一个较早的位置 x。新位置 y 在它后面，而且：

dp[y] <= dp[x]

那么 x 可以删掉。

因为 y 的代价不更大，位置又更靠后。它比 x 更晚离开窗口。未来只要 x 还能参与竞争，y 就一定也在，而且不比它差。

x 没有未来了。

单调队列的队尾维护，本质上是在清理这些已经没有未来、但自己暂时还不知道的候选。

把代码按公式的时间顺序重排，可以写得很直接：

deque<int> q;
q.push_back(0);
dp[0] = 0;

for (int i = 1; i <= n + 1; ++i) {
    while (!q.empty() && q.front() < i - k - 1)
        q.pop_front();

    dp[i] = dp[q.front()] + a[i];

    while (!q.empty() && dp[q.back()] >= dp[i])
        q.pop_back();

    q.push_back(i);
}

每个位置进队一次，最多出队一次。总复杂度 O(n)。

保存下来的原实现把过期清理放在本轮计算之后，为下一轮提前准备，所以边界写成了另一种外观。公式里的 k+1 和代码里的 k 曾经很像一场案发现场。把清理发生的时刻展开，它们其实是同一个不等式。

窗口边界这种东西，它只认生命周期。

街的两头也需要有人留下

还有首尾。

第一个舍弃点之前，也不能连续选超过 k 个。最后一个舍弃点之后，也不能。

可以分别特判。也可以在街的两端安排两个不存在的人：位置 0 和位置 n+1。他们都视为舍弃，代价都是 0。

于是所有真实舍弃点，加上两个虚拟点，满足同一条规则：

相邻点距离 <= k + 1

最终的 dp[n+1] 就是最小舍弃和。答案为：

S - dp[n+1]

严格来说，当 k=n 时，所有真实位置都可以被选中。此时负责“不被选中”的只有虚拟终点 n+1，代价为零。标题没有推翻边界条件。标题把活交给了一个不存在的人。

虚拟节点是个好东西！

虚拟让真实服从秩序。

一次推导，隔了十一天才真正属于自己

现有学习记录里，这道题不是即刻解决的。

7 月 27 日，单调队列理论刚学完，公式已经在引导下推过一次。8 月 7 日，才独立完成模型、代码、边界和对拍。前后十一天。

这更像真实学习。

第一次，我们能听懂一种语言。

第二次，没有字幕了，还能把话说出来。

当时的测试记录写了 2000 组，仓库里后来保存的脚本写了 3000 轮。原始终端输出没留下，所以没必要把两个数字焊成一段辉煌历史。现在重新编译保存的程序，用直接枚举选择子集的暴力程序检查了 8 个边界用例和 3000 组固定种子随机数据，又补了 n=100000 的大值测试。

更重要的是，暴力程序没有使用“总和减舍弃和”。它直接按题意枚举谁被选中、连续选了几个。两套模型得到同一个答案。交叉验证！

下一次，先找谁让连续段停下来

“正难则反”是一句有用的话，也很容易变成废话。

更具体的操作是：

1. 题目是不是在限制某种连续行为？
2. 什么事件会把这段连续行为打断？
3. 能不能不记录连续了多久，只记录最近一次在哪里被打断？
4. 打断事件之间的距离，会不会形成一个固定窗口？
5. 目标函数能不能改写成打断这些位置所付出的代价？

如果这五个问题能接上，状态维度可能会突然塌掉一层。

不是因为 DP 被优化了。

是因为我们终于没有继续用题面的语法思考。

街上的庆典最后正常举行。大部分人都出门了。留下的人坐在门口，看火，看家，看财政大臣那张已经没什么用的 n*k 大表。

总得有人不被选中。

有时候，那个人就是状态。

发布信息草案

• 采用标题：太阳照常升起，总有人不被选中
• 信息型标题：P2034 选择数字：用断点重写连续约束
• 叙事型标题：总得有人不被选中
• 抽象型标题：状态还在数人头，消防大臣已经下班了
• 一句话摘要：当题目限制连续选择长度时，与其追踪连续了多久，不如记录是谁把它打断。
• 标签：动态规划、单调队列、补集、状态设计、元认知