読者です 読者をやめる 読者になる 読者になる

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;

	}
}