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