SRM 656 Div. 1 Easy: RandomPancakeStack (DP・期待値)

解法

dp[i][j]:= i番目にjのパンケーキが置かれる確率を3重ループを回して求めておき、最後に各パンケーキの美味しさを期待値を出す。

1310 -> 1473 (+163)

コード

import java.util.Arrays;

public class RandomPancakeStack {

	public double expectedDeliciousness(int[] d) {
		int N = d.length;
		double[][] dp = new double[N][N];
		Arrays.fill(dp[0], (double) 1 / N);
		for (int i = 0; i < N - 1; i++) {
			for (int j = 0; j < N - i; j++) {
				for (int k = 0; k < j; k++) {
					dp[i + 1][k] += (double) dp[i][j] / (N - i - 1);
				}
			}
		}

		double ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ans += dp[i][j] * d[j];
			}
		}

		return ans;
	}
}