AOJ 0232 Life game
問題
解法
dp。
dp[i][j] := iマス目でお金をjだけ持っている確率
で解く
心臓に悪いコード
int main(){ while(scanf("%d%d%d", &X, &Y, &Z) && X+Y+Z){ memset(dp, 0, sizeof(dp)); memset(m, 0, sizeof(m)); rep(i, X) scanf("%d", V+i); rep(i, Z){ scanf("%d%d%d", &N, &E, &A); m[N][0] = E; m[N][1] = A; } dp[0][0] = 1; rep(i, Y) rep(j, 8192) rep(k, X){ if(i + V[k] >= Y) dp[Y][j] += dp[i][j]/X; else if(m[i + V[k]][0] == 1) dp[min(Y, i+V[k]+m[i+V[k]][1])][j] += dp[i][j]/X; else if(m[i + V[k]][0] == 2) dp[i+V[k]][j+m[i+V[k]][1]] += dp[i][j]/X; else if(m[i + V[k]][0] == 3) dp[i+V[k]][max(0, j-m[i+V[k]][1])] += dp[i][j]/X; else dp[i+V[k]][j] += dp[i][j]/X; } double res = 0; rep(i, 8192) res += dp[Y][i] * i; printf("%d\n", (int)res); } return 0; }