[贪心] [单调队列优化dp] P5665 划分
_Cheems
·
·
个人记录
题意
给出一个长为 n 的序列 a，你可以将其分为若干段。定义 S_i 表示每段的和，需使得 \forall S_{i-1} \le S_i。求 \min{\sum Si^2} ？
思路
关键在于 S_{i-1}\le S_i 的约束。为了描述状态，我们需要定义 f_{i,j} 表示最后一段为 [i,j] 时的最小值。
只能过前 9 个点。
仔细想想，假设一开始没有划分，那么总值为 $V$。现在划分 $l$，使得总值变为 ${v_1} ^2 + {v_2}^2$，且 $V=v_1+v_2$。由完全平方公式可得，多划分肯定更优。
那我们看看划分次数为 $1$ 的时候，划分哪里比较好？众所周知，平方函数的增长速率是不断增大的，那么应让 $v_2-v_1$ 尽量小，所以应该在最右侧满足 $v_1\le v_2$ 的位置划分。
而且这个结论还能拓展到划分次数更多的情况。可以这样简单理解下：
1. 由于最后一段的和是上界，所以在总和不变的情况下，上界越小，段数越多。这恰恰符合一开始的推理。
2. 由于最后一段的和尽量小，所以对于后面的限制也更小，后面的上界也能尽量小。又绕回 $1$ 了。
目前为止已经可以说服我自己了，而且可以通过打表得到验证。[详细证明1](https://matthew99.blog.uoj.ac/blog/5299)，[详细证明2](https://www.luogu.com.cn/blog/command-block/csp2019-ti-xie)，也算是留给自己一个思考题了。
综上，我们可以开一个辅助数组 $ma_i$ 记录 $[1,i]$ 最优划分中最后一段的最小值，$f_i$ 直接记录 $[1,i]$ 最小代价即可。
当 $ma_j\le s_i-s_j$ 时转移：
$$f_j+(s_i-s_j)^2 \to f_i$$
复杂度 $O(n^2)$。
[提交记录](https://www.luogu.com.cn/record/131818332)，又黑又紫。
* #### 单调队列优化
首先，我们不需要关注 $f_j$ 的取值，只需找到满足条件的 $\max j$ 即可。
然后观察转移条件，移项得 $ma_j+s_j\le s_i$。由于左侧与 $i$ 无关，可以考虑单调队列优化。
接着套路地想个单调性质：$i<j$ 且 $ma_i+s_i>ma_j+s_j$，则 $i$ 一定劣于 $j$ 可以被删去。
那么令队中元素满足下标升序，$ma_j+s_j$ 升序。插入很简单，从队尾开始比较 $ma_i+s_i$，由性质得这样干没问题。
如何找 $\max j$ ？不可能每次从头遍历一次。注意到 $s_i$ 单调递增，也就是说假如队中元素无法成为 $i$ 的决策，那么也一定不会成为之后的决策。所以只需找到队中的决策点，保留它并删去它之前的元素即可。
（其实就是性质应用于队头）
* #### 毒瘤出题人
首先如果不写高精的话，就必须用 `__int128`。
然鹅，$n\le4e7$。就算只开一个 `__int128` 数组也会爆，考虑如下简单优化：
1. `f` 数组记录从哪转移而来，这样用 `int` 即可。
2. 除 `s,ma` 外都用 `int`。
[提交记录](https://www.luogu.com.cn/record/131853044)