TopCoder SRM 509 Div1 Medium: PalindromizationDiv1
解法
文字列の長さ伸びたり縮んだりする気がするが、例えば右端にaddする場合は左端と同じ文字をaddするので、操作を重ねるごとに考えるべき文字列は縮んでいく。メモ化再帰で求めれば良い。
コード
import java.util.Arrays; public class PalindromizationDiv1 { private long[] addCost, eraseCost; private long[][] changeCost; private final int L = 26; private final long INF = Integer.MAX_VALUE; private long[][] dp; private char[] string; public int getMinimumCost(String word, String[] operations) { int N = word.length(); // 配列の初期化 addCost = new long[L]; Arrays.fill(addCost, INF); eraseCost = new long[L]; Arrays.fill(eraseCost, INF); changeCost = new long[L][L]; for (int i = 0; i < L; i++) { Arrays.fill(changeCost[i], INF); changeCost[i][i] = 0; } // データの整理 string = word.toCharArray(); for (String string : operations) { String[] s = string.split(" "); if (s[0].equals("add")) { addCost[s[1].charAt(0) - 'a'] = Integer.parseInt(s[2]); } else if (s[0].equals("erase")) { eraseCost[s[1].charAt(0) - 'a'] = Integer.parseInt(s[2]); } else { int from = s[1].charAt(0) - 'a'; int to = s[2].charAt(0) - 'a'; // from->toの有向グラフなのでto->fromは成り立たないことに注意する changeCost[from][to] = Integer.parseInt(s[3]); } } // ワーシャルフロイト for (int k = 0; k < L; k++) { for (int i = 0; i < L; i++) { for (int j = 0; j < L; j++) { changeCost[i][j] = Math.min(changeCost[i][j], changeCost[i][k] + changeCost[k][j]); } } } for (int i = 0; i < L; i++) { for (int j = 0; j < L; j++) { // add iとadd j->iを比べる addCost[i] = Math .min(addCost[i], addCost[j] + changeCost[j][i]); // erase i と i->j eraseを比べる eraseCost[i] = Math.min(eraseCost[i], changeCost[i][j] + eraseCost[j]); } } dp = new long[N + 1][N + 1]; for (int i = 0; i <= N; i++) { Arrays.fill(dp[i], -1); } long ans = dfs(0, N - 1); if (ans == INF) { return -1; } return (int) ans; } private long dfs(int left, int right) { if (left >= right) { return 0; } if (dp[left][right] != -1) { return dp[left][right]; } long min = INF; int strLeft = string[left] - 'a'; int strRight = string[right] - 'a'; min = Math.min(min, eraseCost[strLeft] + dfs(left + 1, right)); min = Math.min(min, dfs(left, right - 1) + eraseCost[strRight]); min = Math.min(min, addCost[strRight] + dfs(left, right - 1)); min = Math.min(min, dfs(left + 1, right) + addCost[strLeft]); for (int letter = 0; letter < L; letter++) { min = Math.min(min, changeCost[strLeft][letter] + dfs(left + 1, right - 1) + changeCost[strRight][letter]); min = Math.min(min, changeCost[strLeft][letter] + dfs(left + 1, right) + addCost[letter]); min = Math.min(min, addCost[letter] + dfs(left, right - 1) + changeCost[strRight][letter]); } dp[left][right] = min; return min; } }