题解：AT_arc195_d [ARC195D] Swap and Erase

george0929 · 2025-11-22 15:36:59 · 题解

被蓝题击败了，怎么回事呢？

各种 DP 直接做都行不通，考虑分析性质。

答案是交换次数加上相同值连续段个数。

分析性质没有思路时，不妨先考虑特殊情况。

如果只允许交换一个数，段数最多减少 2，欲使答案减少，这个数被交换次数最多不超过 1。

假设最优解形态存在一个数被交换多次，先把这个数调回原位，之后只调整这个数必定能得到最优解，而只有一个数能交换的情况就是上述分析的情况。

存在多个数被交换多次可以按上述方法调整证明。

因此直接 DP 即可。dp_{i,0/1} 表示 [1,i]，i 是否和前面数交换的答案。