P2300 合并神犇 笔记

设 $f_i$ 表示考虑到前 $i$ 个数的答案，$p_i$ 表示以 $i$ 为结尾时，合并后的序列最后一个数是几，$s_i$ 是前缀和。

$f_i$ 能从 $f_j$ 转移，当且仅当 $p_j\le s_i-s_j$。

故 $f_i=\underset{s_i\ge s_j+p_j}{min}{f}_j+1$。

单调队列优化。

反思

要把 $0$ 放进单调队列里，否则只有 $1$ 能因越界从 $0$ 转移。