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$。可能都一样。） 考虑如下情况： $$\begin{aligned} 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$ 的配对，都

文章操作