One-Use Switch

스위치 수를 $M=N-1$이라 하고 스위치 $i$의 작동 시각을 $T_i$라 하자. 인접한 스위치의 선후관계를

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

로 나타낸다. 같은 부호열을 가진 두 전체 순서는 서로 겹치지 않는 스위치의 교환만으로 바뀌므로 결과와 비용이 같다. 반대로 경로에 방향을 준 그래프는 항상 DAG이므로 모든 부호열이 실제 순서로 실현된다.

가상 부호 $\varepsilon_0=\downarrow$, $\varepsilon_M=\uparrow$를 둔다. 스위치 $i$에 대해

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

라 하자. 스위치 $i$가 실제로 만나는 두 원본 카드는 처음 위치 $p_i+1$과 $q_i+1$에 있던 카드다. 따라서 비용 발생 여부는 $S_{p_i+1}\mathbin{\mathrm{XOR}}S_{q_i+1}$이다.

부호를 왼쪽부터 결정하면 아직 닫히지 않은 연속 하강 구간의 오른쪽 원본 카드는 미래의 첫 상승 바로 오른쪽 카드다. 정확한 위치는 필요 없고 색 $0$ 또는 $1$만 필요하다.

다음 네 DP 값을 유지한다.

• $U_c$: 열린 하강 구간이 없고 다음 스위치의 왼쪽 원본 카드 색이 $c$일 때의 최소 비용.
• $D_z$: 하강 구간이 열려 있고 그 공통 미래 오른쪽 카드 색을 $z$라고 가정했을 때의 최소 비용.

현재 스위치를 $i$, $a=S_i$, $b=S_{i+1}$라 하자. 상승을 고르면 $U_c$에서 $C_i[c\neq b]$를 더해 $U_c$로 가고, $D_b$에서 $C_i[a\neq b]$를 더해 $U_a$로 간다. 하강을 고르면 $U_c$에서 각 $z$에 대해 $C_i[c\neq z]$를 더해 $D_z$로 가고, $D_z$에서 $C_i[a\neq z]$를 더해 $D_z$로 간다.

$U_{S_1}=0$으로 시작한다. 마지막 실제 스위치에서는 가상 상승을 강제하므로 상승 전이만 수행한다. 답은 마지막의 $\min(U_0,U_1)$이다. 시간 복잡도는 $O(N)$, 문자열 외 추가 메모리는 $O(1)$이다.

Solution written by GPT5