自动搬运

查看原文

来自洛谷，原作者为

	weifengzhaomi 加油，不要辜负对朱前泰说的话

搬运于2025-08-24 23:17:40，当前版本为作者最后更新于2025-06-07 15:22:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路：

看完题目后，应该都能知道这是一道 DP 题。

设状态

设 $dp_{i,j,k}$ 表示第 $k$ 秒后，在 $(x,y)$ 的概率。

设转移

如果当前位置为 $(x,y)$ 的话，那么，按照题目的做法，一共有三种走法，如此，把每种走法都加到一起，再乘一个 $\frac{1}{3}$ 就是走到当前位置的概率。

则有转移状态：

$$dp_{i,j,k} = \frac{1}{3}(dp_{x−1,y,z−1}+dp_{x,y−1,z−1}+f_{x−1,y−1,z−1}) $$

接下来，枚举每个位置，求出到这个位置的概率，最后求和就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
double dp[210][210][210],ans;
int n;
signed main(){
	scanf("%d",&n),dp[0][0][0] = 1;
	for (int i = 1;i <= n;i++)
		for (int j = 0;j <= n;j++)
			for (int k = 0;k <= n;k++){
				if (j > 0) dp[j][k][i] += dp[j - 1][k][i - 1];
				if (k > 0) dp[j][k][i] += dp[j][k - 1][i - 1];
				if (j > 0 && k > 0) dp[j][k][i] += dp[j - 1][k - 1][i - 1];
				dp[j][k][i] /= 3.0;
			}
	for (int i = 0;i <= n;i++)
		for (int j = 0;j <= n;j++) ans += dp[i][j][n] * sqrt(i * i + j * j);
	printf("%.9lf\n",ans);
}