Codeforces Round #114 (Div. 1) B : Wizards and Huge Prize
問題概要
よく分からない。
解法
状態がN^3程度に収まるように注意しながらDPする。
acceptされたコード
この問題では気にしなくても大丈夫だけど、非正規化数でTLEしないように注意。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 200; const int MAX_L = 200; const int MAX_K = 200; int N, K, L, FULL; double dp[MAX_N + 1][MAX_N + 1][2 * MAX_N + 2]; int ps[MAX_N], as[MAX_N]; void init(){ scanf("%d%d%d", &N, &L, &K); for(int i=0; i<N; ++i){ scanf("%d", ps+i); } for(int i=0; i<N; ++i){ scanf("%d", as+i); } FULL = N; } double solve(){ if(K > FULL){ K = FULL; } dp[0][0][K+N] = 1.0; FULL += N; for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ for(int k=0; k<FULL; k++)if(dp[i][j][k] > 1e-100){ if(as[i] == -1){ if(k > 0){ dp[i+1][j+1][k - 1] += dp[i][j][k] * (ps[i] / 100.0); } dp[i+1][j][k] += dp[i][j][k] * ((100 - ps[i]) / 100.0); } else{ dp[i+1][j+1][min(FULL, k + as[i])] += dp[i][j][k] * (ps[i] / 100.0); dp[i+1][j][k] += dp[i][j][k] * ((100 - ps[i]) / 100.0); } } //FULLの場合 if(dp[i][j][FULL] > 1e-100){ dp[i+1][j+1][FULL] += dp[i][j][FULL] * (ps[i] / 100.0); dp[i+1][j][FULL] += dp[i][j][FULL] * ((100 - ps[i]) / 100.0); } } } double ret = 0.0; for(int i=L; i<=N; i++){ for(int j=N; j<=FULL; j++){ ret += dp[N][i][j]; } } return ret; } int main(){ init(); printf("%.8f\n", solve()); return 0; }