706C. Hard problem

보통 제목은 반대인 경우가 많다.

Problem - 706C - Codeforces

---

문자열을 사전 순으로 정렬하는 문제인데, 특이하게도 문자열의 순서를 바꿀 수 없다는 제한이 있다. 대신 문자열을 앞뒤로 뒤집는 연산만 가능하다. 또, 뒤집는 비용도 문자열마다 모두 다르다. 이제 문자열을 정렬하는 데 드는 최소 비용을 계산해 보자.

 

문제에서 사전 순서대로 정렬하라고 했으므로, 앞에서부터 오름차순으로 정렬해야 한다.

 

$cur$번 문자열을 뒤집는 상태가 $s$일 때, $cur$부터 끝까지 정렬하는 데 드는 최소 비용을 $dp(cur,~s)$라고 하자. $cur$번 문자열을 뒤집는다면 $s=1$이고, 뒤집지 않는다면 $s=0$이다.

 

$cur$번 문자열에서 드는 비용을 $cur\_cost$라고 하면 $cur\_cost=\begin{cases}cost[cur] & (s = 1)\\0 & (s = 0)\end{cases}$이다. 이제 $cur+1$번 문자열을 뒤집거나 뒤집지 않았을 때 사전 순으로 정렬이 가능한지 확인하고, 정렬이 가능하다면 해당 경우의 값을 재귀적으로 얻어오면 된다.

 

식으로 나타내면 다음과 같다.

 

$dp(cur,~s)=\begin{cases} {\min(dp(cur+1,~0),~dp(cur+1,~1))+cur\_cost}& (s = 1)\\{\min(dp(cur+1,~0),~dp(cur+1,~1))} & (s=0)\end{cases}$

 

단, 정렬이 되는지 먼저 확인한 후에 재귀를 호출해야 한다.

---

한번에 맞힘 히히