AK-dream

火山喷发

AK-dream

发布于：2019年8月27日
次浏览

【题目描述】
火山喷发对所有附近的生物具有毁灭性的影响。在本题中，我们希望用数值来模拟这一过程。
在环境里有$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;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/40a07a47.html/

更新于：2020年9月7日

动态规划

概率DP

评论