Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

AOJ0232:Life Game

久々にDPを全部自力で解けた。

方針

dp[i][j] := i-thマスに得点jで来る確率
としてDP。
マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに
入れるという発想が出てきた。
加えて戻ることはないのでDAGになるはず。

進む場合はゴールを超えてしまわないように、
減点される場合は0以下にならないように気をつける。

答えはΣ_i(dp[n][i] * i)を計算すればよい。
あとは小数切捨てなので間違えないように。

以下ソースコード

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>

using namespace std;

#define KIND first
#define VALUE second
#define MAX_STOPS 101
#define MAX_VALUE 10001

double dp[MAX_STOPS][MAX_VALUE];

int main(){
	int x,y,z; //x:=# of kind of eyes y:= # of stops z:=# of event stops
	
	while(cin >> x >> y >> z){
		if(!(x|y|z)) break;
		vector<int> dice(x);
		pair<int,int> stops[y+1]; //
		
		//initialize
		for(int i=0;i<x;i++){
			cin >> dice[i];
		}
		
		fill((pair<int,int> *)stops, (pair<int,int> *)stops + y + 1, make_pair(0,0));
		
		for(int i=0;i<z;i++){
			int pos,kind,val;
			cin >> pos >> kind >> val;
			stops[pos].KIND = kind;
			stops[pos].VALUE = val;
		}
		
		fill((double *)dp, (double *)dp + MAX_STOPS * MAX_VALUE, 0);
		dp[0][0] = 1;
		for(int i=0;i<y;i++){
			for(int j=0;j<MAX_VALUE;j++){
				if(dp[i][j] == 0) continue;
				for(int k=0;k<x;k++){
					int next = i + dice[k],val;
					if(next >= y) next = y;
					if(stops[next].KIND == 2){ //add+
						dp[next][j + stops[next].VALUE] += dp[i][j] / x;
					}else if(stops[next].KIND == 3){ //sub
						val = j - stops[next].VALUE <= 0?0:j-stops[next].VALUE;
						dp[next][val] += dp[i][j] / x;
					}else if(stops[next].KIND == 1){ //proceed
						next += stops[next].VALUE;
						if(next >= y) next = y;
						dp[next][j] += dp[i][j] / x;
					}else{
						dp[next][j] += dp[i][j] / x;
					}
				}
			}
		}
		double e = 0;
		for(int i=0;i<MAX_VALUE;i++){
			e += i * dp[y][i];
		}
		int ret = e;
		cout << ret << endl;
	}
}