P6631 [ZJOI2020] 序列

可以将问题用形象地方式来表述。给定一排点，第 \(i\) 个点有它需要的覆盖次数 \(a_i\)。有两种线段，一种能覆盖连续的一些点，称其为连续线段；另一种能覆盖相邻间隔为 \(1\) 的一些点，称其为间隔线段。现在要用尽可能少的线段覆盖所有点 \(i\) 恰好 \(a_i\) 次。

发现如果没有间隔线段就是被某组织出烂的原题。显然，每次取最长的非 \(0\) 段最优。

回到本题，首先可以证明一个结论：假设 \(a_1\sim a_i>0\)，\(a_{i+1}=0\) 且 \(i>1\)，选一条从 \(1\sim i\) 的连续线段一定不劣。因为选择间隔线段虽然可以延伸到 \(i+2\) 但需要两条，而选连续线段完全可以加一条 \(i+2\) 开头的，还能自行选择类型。

接着需要怎么做呢？唯一需要考虑的就是前面有线段连过来。在处理点 \(i\) 时，记连过来的连续线段数量为 \(x\)，能覆盖到点 \(i\) 的间隔线段数量为 \(y\)，不能覆盖到点 \(i\) 的间隔线段数量为 \(z\)。

先处理一下特殊情况：连过来的线段太多了，即 \(x+y>a_i\)，有 \(k\gets x+y-a_i\) 条线段不能向后继续延伸。但我们会发现留下间隔线段还是连续线段是根据后面的情况决定的，所以不妨将 \(x\gets x-k\)，\(y\gets y-k\)，标记置为 \(k\)，表示可以免费连向后面的线段数量（种类任选）。但这样可能会出现一种情况，\(x<k\) 或 \(y<k\)，此时标记就不合法了。对于这种情况，我们将较少的那种线段数量置为 \(0\)，较多的线段数量对应减少，即可保证合法。

然后就好办了，根据之前的结论处理 \(a_{i-1}\) 与 \(a_i\)。能用连续线段就用，如果 \(i-1\) 还有剩下就用间隔线段。

当然还要一些需要注意的细节：

• 如果更新了标记，最后需要将 \(a_i\) 置为 \(k\)，答案减去 \(k\)，同时清空标记。这样就实现了免费连。
• 从 \(i=2\) 开始做。
• 最后多做一次。

好像不能叫反悔贪心，因为只是暂时不做。