zoj 3640(概率期望DP)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}
------ 本文结束 ------