zoj 3640(概率期望DP)

zoj 3640
设$dp(u)$为力气值为$u$时的逃离期望。
当$u \leq c(i)$时可以转移到$dp(u+c(i))$，否则$dp(u)$可以直接加上$t(i)$
显然记忆化搜索好写，直接写记忆化搜索即可，递推其实也可以的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 10000 + 5;
const db xs = (1.0 + sqrt(5)) / 2.0;
int n, f, ci[MAXN];
db dp[MAXN*2];
db dfs(int u) {
    if (dp[u]>=0) return dp[u];
    dp[u] = 0;
    for (int i=1;i<=n;i++) {
        if (u > ci[i]) {
            dp[u] += (int)(ci[i] * ci[i] * xs);
        } else dp[u] += dfs(u + ci[i]) + 1;
    }
    dp[u] *= 1.0 / (db)n;
    return dp[u];
}
void clean() {
    ms(dp, -1);
}
void solve() {
    clean();
    for (int i=1;i<=n;i++) scanf("%d", &ci[i]);
    printf("%.3f\n", dfs(f));
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n, &f)==2) solve();
    fclose(stdin); fclose(stdout);
    return 0;
}