SRM 381 250pt: TheDiceGame

問題概要

サイコロを振ったら出た目の数だけ飴がもらえる。飴をC(<10^6)個以上もらうのに必要なターン数の期待値を求める問題。

考えたこと

• DP臭。
• まだよく分かっていない。

後から解いたコード

計算量O( 6 * C )。

const int MAX_N = 1000000;
double dp_ins[MAX_N + 10];

struct TheDiceGame {

	double expectedThrows(int candies) {
		double *dp = dp_ins + 6;
		for(int cur=1; cur<=candies; cur++){
			for(int d=1; d<=6; d++){
				dp[cur] += 1.0/6.0 * (1.0 + dp[cur - d]);
			}
		}
		return dp[candies];
	}

};