ZOJ 3640 Help Me Escape

题意：一个人在迷宫里面，这个人有f的攻击力。他一共有n条通道可供随机选择，每次等概率随机选择一条。对每条通道i有参数c[i]。选择通道k后，若f > c[k]，则花费时间t[k]逃出迷宫，否则花费一天，攻击力f增加c[k]，且一天之后继续选择通道。求逃出去所花费的天数的期望。其中t[k] = (int)((1+√5) * c[k]*c[k] / 2)。

解法：概率DP加记忆化写法。设d[i]表示当攻击力为i逃出去所花费的天数的期望，遍历每个通道j，若i > c[j]则d[i] += t[j] / n，否则d[i] += (1 + d[i+c[j]]) / n。

tag:概率DP，记忆化

/*
 * Author:  Plumrain
 * Created Time:  2013-11-16 19:38
 * File Name: DP-ZOJ-3640.cpp
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int n, f;
int c[10005];
double x;

double DP(int f)
{
    double ret = 0.0;
    for (int i = 1; i <= n; ++ i){
        if (f > c[i]) ret += (int)(x * c[i] * c[i]);
        else ret += 1 + DP(f+c[i]);
    }
    ret /= (double)n;
    return ret;
}

int main()
{
    x = (1 + sqrt(5)) / (double)2;
    while (scanf ("%d%d", &n, &f) != EOF && n){
        for (int i = 1; i <= n; ++ i)
            scanf ("%d", &c[i]);
        printf ("%.3f
", DP(f));
    }
    return 0;
}