0232:Life Game

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232

動的計画法で解いた。

dp[マスの番号][所持金]:=マス i に所持金 j で行ける確率

とすると、

人生ゲームにイベントマスがなければ
dp[i + v[k] ][j] += dp[i][j]/x

v[k]はルーレットの数字。xはルーレットの数字の個数。

イベントを考えると、

イベント1　aだけ進む
dp[ i + v[k] + a ][j] += dp[i][j]/x

イベント2　お金a円をゲット
dp[ i + v[k] ][ j + a ] += dp[i][j]/x

イベント3　お金a円を失くした
dp[ i + v[k] ][ j - a ] += dp[i][j]/x

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

struct M{int e,a;};

int main(void){
	
	int x,y,z,n;
	double dp[51][5001];
	M in;
	map<int,M>m;
	
	while(cin >> x >> y >> z,x|y|z){
		vector<int>v(x);
		m.clear();
		
		for(int i=0;i<x;i++)cin >> v[i];
		for(int i=0;i<z;i++){
			cin >> n >> in.e >> in.a;
			m[n]=in;
		}
		
		fill(dp[0],dp[51],0);
		dp[0][0]=1;
		
		for(int i=0;i<y;i++){
			for(int j=0;j<5001;j++){
				for(int k=0;k<x;k++){
					int nx=i+v[k];
					if(m[nx].e==1)dp[min(y,nx+m[nx].a)][j]+=dp[i][j]/x;
					else if(m[nx].e==2)dp[nx][j+m[nx].a]+=dp[i][j]/x;
					else if(m[nx].e==3)dp[nx][max(0,j-m[nx].a)]+=dp[i][j]/x;
					else dp[min(y,nx)][j]+=dp[i][j]/x;
				}
			}
		}
		double ans=0;
		for(int j=0;j<5001;j++)ans+=dp[y][j]*j;
		
		cout << (int)ans << endl;
	}
	
return 0;
}