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