이동식 저장소

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

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

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

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

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

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

$dp(cur,s)=\{\begin{array}{ll}min(dp(cur+1,0),dp(cur+1,1))+cur\mathrm{\_}cost& (s=1)\\ min(dp(cur+1,0),dp(cur+1,1))& (s=0)\end{array}$

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

한번에 맞힘 히히