AK-dream

【题目描述】
火山喷发对所有附近的生物具有毁灭性的影响。在本题中,我们希望用数值来模拟这一过程。
在环境里有 $n$ 个生物分别具有 $A_1,A_2,\cdots,A_n$点生命值,一次火山喷发总计 $M$ 轮,每轮造成 $1$ 点伤害,等概率地分给所有存活的生物,即如果目前有 $K$ 个活着的生物,每个生物受到这点伤害的概率是 $\frac{1}{K}$。如果一个生物的生命值减为 $0$,它会立即死去,此后都不会再占用受到伤害的概率。如果没有生物存活,那么将没有生物会受到伤害。
现在你的任务是,给定 $n,M$ 和全部生物的生命值,问每个生物火山喷发后依然存活的概率。

【输入格式】
第一行两个正整数 $n$ 和 $M$。
第二行 $n$ 个正整数 $A_1,\cdots,A_n$。

【输出格式】
$n$ 行,第 $i$ 行一个数表示第 $i$ 个生物存活下来的概率,保留小数点后六位。

【数据范围】
对于全部数据 $n \le 4$, $M \le 120$,$A_i\le50$。


挺水的
突破口在于$n \le 4$,可以直接建数组$f[i][j][k][l]$表示生物1有$i$生命,生物2有$j$生命,$3$->$k$, $4$->$l$的概率
然后就可以枚举轮数,枚举$i, j, k$来进行DP了,注意$l$不需要枚举,因为每个轮数及$i, j, k$正好对应一个$l$。
转移方程很简单吧。。。文字不太好表示,看代码吧
时间复杂度$O(120*50^{3})$;

【代码】

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
using namespace std;

int n, m, sum, a[10];
double dp[51][51][51][51], ans[10];

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
m = min(m, sum);
dp[a[1]][a[2]][a[3]][a[4]] = 1;
for (int tme = 0; tme <= m; tme++) {
for (int i = 0; i <= a[1]; i++) {
for (int j = 0; j <= a[2]; j++) {
for (int k = 0; k <= a[3]; k++) {
int l = sum - tme - i - j - k;
if (sum - i - j - k - l != tme) continue;
if (l > a[4] || l < 0) continue;
if (i == 0 && j == 0 && k == 0 && l == 0) continue;
int num = 0;
if (i) num++; if (j) num++; if (k) num++; if (l) num++;
if (i) dp[i-1][j][k][l] += dp[i][j][k][l] / num;
if (j) dp[i][j-1][k][l] += dp[i][j][k][l] / num;
if (k) dp[i][j][k-1][l] += dp[i][j][k][l] / num;
if (l) dp[i][j][k][l-1] += dp[i][j][k][l] / num;
}
}
}
}
//统计答案写得恶臭无比 不要在意
for (int i = 0; i <= a[2]; i++) {
for (int j = 0; j <= a[3]; j++) {
for (int k = 0; k <= a[4]; k++) {
if (sum - i - j - k == m) {
ans[1] += dp[0][i][j][k];
}
}
}
}
for (int i = 0; i <= a[1]; i++) {
for (int j = 0; j <= a[3]; j++) {
for (int k = 0; k <= a[4]; k++) {
if (sum - i - j - k == m) ans[2] += dp[i][0][j][k];
}
}
}
for (int i = 0; i <= a[1]; i++) {
for (int j = 0; j <= a[2]; j++) {
for (int k = 0; k <= a[4]; k++) {
if (sum - i - j - k == m) ans[3] += dp[i][j][0][k];
}
}
}
for (int i = 0; i <= a[1]; i++) {
for (int j = 0; j <= a[2]; j++) {
for (int k = 0; k <= a[3]; k++) {
if (sum - i - j - k == m) ans[4] += dp[i][j][k][0];
}
}
}
for (int i = 1; i <= n; i++) {
printf("%.6lf\n", 1 - ans[i]);
}
return 0;
}


 评论