SRM 653 Div. 2 Hard: SingingEasy（動的計画法）

問題

TopCoder Statistics - Problem Statement

解法

動的計画法を使う。アリスが最後に歌った曲とボブが最後に歌った曲に対応する難易度の最小値をメモしておく。

コード

public class SingingEasy {

	public int solve(int[] pitch) {
		int N = pitch.length;
		if (N < 3) {
			return 0;
		}
		int[][] dp = new int[N + 1][N + 1];
		// dp[i+1][j+1]:= アリスがi、ボブがjを歌った後の難易度の最小値
		for (int n = 2; n <= N; n++) {
			dp[0][n] = dp[0][n - 1] + Math.abs(pitch[n - 1] - pitch[n - 2]);
			dp[n][0] = dp[n - 1][0] + Math.abs(pitch[n - 1] - pitch[n - 2]);
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j) {
					continue;
				}

				if ((i == 2 && j == 1) || (i == 1 && j == 2)) {
					continue;
				}

				if (i == j + 1) {
					dp[i][j] = dp[0][j];
					for (int k = 1; k < i - 1; k++) {
						if (k == j) {
							continue;
						}
						dp[i][j] = Math.min(dp[i][j], dp[k][j] + Math.abs(pitch[i - 1] - pitch[k - 1]));
					}
				} else if (i + 1 == j) {
					dp[i][j] = dp[i][0];
					for (int k = 1; k < j - 1; k++) {
						if (i == k) {
							continue;
						}
						dp[i][j] = Math.min(dp[i][j], dp[i][k] + Math.abs(pitch[j - 1] - pitch[k - 1]));
					}

				} else {
					dp[i][j] = 1000000000;
					if (j >= 2) {
						dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + Math.abs(pitch[j - 1] - pitch[j - 2]));
					}
					if (i >= 2) {
						dp[i][j] = Math.min(dp[i - 1][j] + Math.abs(pitch[i - 1] - pitch[i - 2]), dp[i][j]);
					}
				}
			}
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			min = Math.min(min, dp[N][i]);
		}
		for (int i = 0; i < N; i++) {
			min = Math.min(min, dp[i][N]);
		}

		return min;
	}
}