One-Use Switch

Let $M=N-1$, and let $T_i$ be the time when switch $i$ is operated. Record only the relative order of adjacent switches:

$$\varepsilon_i= \begin{cases} \uparrow,&T_i<T_{i+1},\\ \downarrow,&T_i>T_{i+1}. \end{cases}$$

Two complete orders with the same sign sequence differ only by swaps of disjoint switches, so they have the same result and cost. Conversely, orienting the edges of a path never creates a directed cycle, so every sign sequence is realizable.

Add virtual signs $\varepsilon_0=\downarrow$ and $\varepsilon_M=\uparrow$. For switch $i$, define

$$p_i=\max\{j<i:\varepsilon_j=\downarrow\},\qquad q_i=\min\{j\geq i:\varepsilon_j=\uparrow\}.$$

The two original cards seen by switch $i$ started at positions $p_i+1$ and $q_i+1$. Thus this switch costs money exactly when $S_{p_i+1}\mathbin{\mathrm{XOR}}S_{q_i+1}=1$.

While deciding signs from left to right, an open descending run shares one future right card: the card immediately to the right of the next upward sign. Its exact position is unnecessary; only its color $0$ or $1$ matters.

Maintain four DP values:

• $U_c$: no descending run is open, and the next switch's left original card has color $c$.
• $D_z$: a descending run is open, assuming its common future right card has color $z$.

At switch $i$, let $a=S_i$ and $b=S_{i+1}$. Choosing an upward sign sends $U_c$ to $U_c$ with cost $C_i[c\neq b]$, and sends $D_b$ to $U_a$ with cost $C_i[a\neq b]$. Choosing a downward sign sends $U_c$ to each $D_z$ with cost $C_i[c\neq z]$, and sends $D_z$ to itself with cost $C_i[a\neq z]$.

Initialize $U_{S_1}=0$. At the last real switch, allow only the upward transition to implement the virtual final sign. The answer is $\min(U_0,U_1)$. The time complexity is $O(N)$ and the extra memory excluding the input string is $O(1)$.

Solution written by GPT5