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; } }