이동식 저장소

보통 제목은 반대인 경우가 많다. Problem - 706C - Codeforces codeforces.com 문자열을 사전 순으로 정렬하는 문제인데, 특이하게도 문자열의 순서를 바꿀 수 없다는 제한이 있다. 대신 문자열을 앞뒤로 뒤집는 연산만 가능하다. 또, 뒤집는 비용도 문자열마다 모두 다르다. 이제 문자열을 정렬하는 데 드는 최소 비용을 계산해 보자. 문제에서 사전 순서대로 정렬하라고 했으므로, 앞에서부터 오름차순으로 정렬해야 한다. $cur$번 문자열을 뒤집는 상태가 $s$일 때, $cur$부터 끝까지 정렬하는 데 드는 최소 비용을 $dp(cur,~s)$라고 하자. $cur$번 문자열을 뒤집는다면 $s=1$이고, 뒤집지 않는다면 $s=0$이다. $cur$번 문자열에서 드는 비용을 $cur\_cos..