TopCoder SRM 318 Div1 Medium CyclicGame

問題

nマスが円状につながったすごろくがある。
通常の6面ダイスを振って、出た目だけ進んで、止まったマスに書かれた数字の点数を得る。
ゲームは（ダイスを振る前に）好きなタイミングで止めることができる。

最善の戦略を取るとき、ゲームで得られる点数の合計の期待値を求めよ。

制約条件

n≦15
-100≦それぞれのマスに書かれている数字≦100
マスの数字を合計すると負になる

方針

収束するまでループをまわす。
dp[i][j]を、i回サイコロを振ってjのマスにいるときの得点の期待値の最大値とすると、
dp[i+1][j]=max(dp[i][j], Σ(dp[i][j+k]+cells[j+k])/6)

まわす回数は1000回あれば十分。

「止まったら終了するマス」を2^15通り決めて、
それぞれの場合について連立方程式を解いてもとけるらしい。

ソースコード

const int MX=1000;
double dp[MX][20];

class CyclicGame {
	public:
	double estimateBank(vector <int> cells) 
	{
		int n=cells.size();
		memset(dp,0,sizeof(dp));
		
		rep(i,MX-1)rep(j,n){
			double tmp=0;
			rep(k,6)tmp+=(cells[(j+k+1)%n]+dp[i][(j+k+1)%n])/6;
			dp[i+1][j]=max(dp[i][j],tmp);
		}
		return dp[MX-1][0];
	}
	
};