题解

思路

处理到当前位置时，过去如何分组只通过两个子序列的末尾值影响未来。把两个尾值排序为 $x\le y$，初始均视为正无穷。

若新值能无惩罚地接在某个尾值后面，应保留对未来更有利的另一尾值；若两个尾值都不能接，则无论如何都必须新增一次惩罚，并应保留较大的旧尾值。

做法

依次处理值 $v$，每次先保证 $x\le y$：

• 若 $v\le x$，两个序列都能零代价接入，令 $x=v$；
• 否则若 $v\le y$，只有第二个序列能零代价接入，令 $y=v$；
• 否则两个尾值都小于 $v$，惩罚加一并令 $x=v$，随后下一轮重新排序。

第一种选择用 $v$ 替换最小的可接尾值，留下更大的尾值；第三种选择替换较小尾值，同样留下更大的旧尾值。

正确性证明

对每个前缀使用交换论证。两个尾值都能接入时，把 $v$ 接到较小尾值所得尾值集合为 $\{v,y\}$；接到较大尾值则为 $\{x,v\}$。因为 $x\le v\le y$，前者逐项不小于后者，对未来提供的零代价接入范围不会更差。

仅较大尾值能接入时选择唯一。两个尾值都小于 $v$ 时必付一次惩罚；替换较小尾值会保留较大的旧尾值，按同一支配关系不劣于替换较大尾值。于是每一步算法都在当前最小代价下保留对未来最优的尾值集合，归纳可知总惩罚最小。

复杂度分析

每个元素只进行常数次比较，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

子任务说明

• $n\le20$ 时枚举全部二元分组。
• $n\le3000$ 时以另一条子序列的尾值为状态做 $O(n^2)$ 动态规划。
• 满数据使用双尾值交换贪心。