题解

思路

最优方案中的交换可以整理成原序列相邻边上的一个匹配，也就是每个元素至多参与一次交换；否则连续参与多次的移动可以被重新安排并消去而不变差。

做法

选定这些互不相邻的交换后，先完成交换再从左到右删除，删除次数正好是新序列的连续段数。于是目标变成最小化“选中的边数 + 交换后相邻不同的边数 + 1”。

从左到右决定每条边是否选入匹配。某个位置最终放的是左邻、自己还是右邻，只取决于它两侧的边是否被选；当扫描到下一条边时，只需记住最近两条边的选择，就能确定一个新的连续段分界并加入代价，同时禁止相邻两条边都被选择。四个状态做常数次转移，末尾补上最后一个分界和基础的一次删除即可。

复杂度

时间复杂度为 $O(N)$，额外空间为 $O(1)$。