Real-Programmer-Game

发表于

一道dp/概率论的题目。

source：北美字节（Tik ToK）的题难到逆天了 - V2EX

description

Real Programmer Game (RPG) is about having a hero swinging sticks at a monster.
The monster has N Health Points (НР). It is killed when HP drops to 0 or negative.
Each swing of the hero reduces monster’s HP by a (evenly distributed) random number in
[0, M].
What’s the probability for the hero to kill the monster in K swings?
Write a function, input N, M, K, return such probability (in [0, 1]).
Constraints
0<=N<= 1000
0<M <= 1000
0<=K<= 1000

题目意思就是求$X_i\sim U(0,M),P(\sum_{i=1}^{K} X_i\ge N)$。

Solution

$X_i$ 只能取整数

dp。

时间复杂度为 $O(M^2K^3)$，可以用前缀和优化到 $O(MK^2)$，空间复杂度使用滚动数组为 $O(MK)$。

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
const int MAXN = 1050, MAXM = 1050, MAXK = 1050;
double f[2][MAXM * MAXK];

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	if (m * k < n)
	{
		printf("0");
		return 0;
	}
	double p = 1.0 / (m + 1);
	for (int i = 0; i <= m; i++)
		f[0][i] = 1.0;
	for (int i = 1; i <= k; i++)
	{
		for (int j = 0; j <= m * i; j++)
		{
			if (j - m <= 0)
				f[1][j] = f[0][j] * p;
			else
				f[1][j] = (f[0][j] - f[0][j-m-1]) * p;
		}
		f[0][0] = f[1][0];
		f[1][0] = 0.0;
		for (int j = 1; j <= m * i; j++)
		{
			f[0][j] = f[1][j] + f[0][j - 1];
			f[1][j] = 0.0;
		}
		for (int j=m*i + 1; j<=m*i+m; j++)
			f[0][j] = f[0][j-1];
	}
	printf("%f", f[0][m * k] - f[0][n - 1]);
	return 0;
}

似乎超时了？

取有理数

秒变数学题。。

当 $N=1$ 时累计分布函数为

欧文–贺尔分布 - 维基百科，自由的百科全书 (wikipedia.org)

建议mathematica解题。UniformSumDistribution—Wolfram 语言参考资料