ZOJ Monthly, August 2012 - H : Help Me Escape

問題概要

解法

力がfのときに脱出までかかる日数の期待値をO(F*N)のDPで計算する。

acceptされたコード

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_F = 10000;
const int MAX_N = 100;

int N, F;

int cs[MAX_N], days[MAX_N];
double expect[MAX_F * 2 + 1];

bool init() {
	if (scanf("%d%d", &N, &F) == EOF) {
		return false;
	}

	for (int i = 0; i < N; ++i) {
		scanf("%d", cs + i);
	}

	return true;
}

double solve() {
	for (int i = 0; i < N; ++i) {
		days[i] = int( (1.0 + sqrt(5.0)) / 2.0 * cs[i] * cs[i] );
	}

	const double chooseProb = 1.0 / N;
	fill(expect, expect + MAX_F * 2 + 1, 0.0);
	for (int f = MAX_F*2; f >= 0; --f) {
		if (f > MAX_F) {
			for (int i = 0; i < N; ++i) {
				expect[f] += days[i];
			}
		}
		else {
			for (int i = 0; i < N; ++i) {
				if (cs[i] < f) {
					expect[f] += days[i];
				}
				else {
					expect[f] += expect[f + cs[i]] + 1.0;
				}
			}
		}
		expect[f] *= chooseProb;
	}
	return expect[F];
}

int main() {
	for (;init();) {
		printf("%.3f\n", solve() + 1e-11);
	}
	return 0;
}