読者です 読者をやめる 読者になる 読者になる

AOJ 0232 Life game

問題

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