1或2序列最小总代价变换操作方案

· · 个人记录

给定长为 n 的序列 S, T，S_i, T_i \in \lbrace 1, 2 \rbrace 且两序列 1 和 2 的数量分别相等。每次操作可以在 S 中选取一个长度不超过 3 的区间，将其中的数左右翻转，操作的代价为区间内数的和加上常数 C。 求一种总代价最小的将 S 变换为 T 的操作序列。

区间长为 2，等价于交换相邻两数；区间长为 3，等价于隔一个数交换两数。只有交换相异的数的操作有意义。于是只会采取下列操作：

\lbrack 1, 2 \rbrack \Leftrightarrow \lbrack 2, 1 \rbrack &\mathrm{cost}=3+C &(a)\\ \lbrack 1, 1, 2 \rbrack \Leftrightarrow \lbrack 2, 1, 1 \rbrack &\mathrm{cost}=4+C &(b_1)\\ \lbrack 1, 2, 2 \rbrack \Leftrightarrow \lbrack 2, 2, 1 \rbrack &\mathrm{cost}=5+C &(b_2)\\ \end{cases}

考虑将 S 中的 2 与 T 中的配对。（不知道为什么不配对 1。可能都一样。）

考虑如下情况：

S&=\lbrace 1,1,1,\underline{1},\underline{1},1,\underline{1},1,\underline{2},1 \rbrace \\ T&=\lbrace 1,1,1,2,1,1,1,1,1,1 \rbrace \end{aligned}

将 S 中 2 挪到 T 中对应位置只需 (b_1) \times 2 + (a) \times 1（位置变动已用下划线标出）。

事实上，对于任意一种 2 的配对，都