标签：期望 int YBT2023 Day3 步数 千与千寻 高斯消

千与千寻

题目链接：YBT2023寒假Day3 A

题目大意

一个 n*m 的平面，你要从 (0,0) 走到 (x,y)，你等概率的向上或向右走，然后当你走到 (n-1,i) 再往右走，就是 (0,i)，走到 (i,m-1) 再往上走，就是 (i,0)。
问你期望需要的步数。

思路

考虑一个直接的想法是直接把每个点都是一个量是它走到 \((x,y)\) 的期望步数，但是量太多了。
考虑特殊的地方，就是传送，那我们需要维护的就只有边界的 \(2(n+m-1)\) 个了。

然后你考虑求从左下角的某个点走到右上角的某个点，期望步数和期望概率，显然随便 DP 一下就有了。
然后考虑列方程：
\(从穿越点过来概率*0.5+从左边/下面的点过来的概率*0.5=这个变量的值+要这么走的期望步数\)
（\(*0.5\) 是因为还要走一步才能过来或者穿越，那个期望步数记得是两个的和）

然后列出式子高斯消元，然后注意最后还要走到 \((x,y)\)，反过来就是从 \((x,y)\sim (0,0)\)。
当然我们还要加上直接不用传送就走到的期望。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 105;
int n, m, x, y;
double g[N][N][N * 2], f[N][N], G[N * 2][N * 2];

double Abs(double x) {return x < 0 ? -x : x;} 

int main() {
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout); 
	
	scanf("%d %d %d %d", &n, &m, &x, &y);
	
	for (int i = 0; i <= n - 2; i++) g[i][m - 1][i + 1] = 1;
	for (int i = 0; i <= m - 2; i++) g[n - 1][i][n + i] = 1;
	for (int i = n - 2; i >= 0; i--)
		for (int j = m - 2; j >= 0; j--) {
			for (int k = 1; k <= n + m - 2; k++) {
				g[i][j][k] = (g[i + 1][j][k] + g[i][j + 1][k]) / 2.0;
			}
			f[i][j] = 1.0 + (f[i + 1][j] + f[i][j + 1]) / 2.0;
		}
	
	int tot = 0;
	for (int i = 0; i <= n - 2; i++) {
		tot++;
		for (int j = 1; j < n + m; j++) G[tot][j] = g[i][0][j] / 2.0;//穿越 
		if (i != n - 2) G[tot][i + 2] += 0.5;//旁边左走 
		G[tot][n + m - 1] = -f[i][0] / 2.0 - 1.0;//期望步数（穿越的加上旁边走的） 
		G[tot][tot]--;//加上自己 
	}
	for (int i = 0; i <= m - 2; i++) {
		tot++;
		for (int j = 1; j < n + m; j++) G[tot][j] = g[0][i][j] / 2.0;
		if (i != m - 2) G[tot][n + i + 1] += 0.5;
		G[tot][n + m - 1] = -f[0][i] / 2.0 - 1.0;
		G[tot][tot]--;
	}
	
	for (int i = 1; i <= tot; i++) {
		int k = i;
		for (int j = i + 1; j <= tot; j++)
			if (Abs(G[j][i]) > Abs(G[k][i])) k = i;
		if (!G[k][i]) while (1);
		swap(G[i], G[k]);
		for (int j = 1; j <= tot; j++) {
			if (i == j) continue;
			double tmp = G[j][i] / G[i][i];
			for (int k = i + 1; k <= tot + 1; k++) {
				G[j][k] -= G[i][k] * tmp;
			}
		}
	}
	
	double ans = 0;
	for (int i = 1; i <= tot; i++)
		ans += g[n - 1 - x][m - 1 - y][i] * G[i][tot + 1] / G[i][i];
	ans += f[n - 1 - x][m - 1 - y];
	printf("%.10lf", ans);
	
	return 0;
}

标签：期望,int,YBT2023,Day3,步数,千与千寻,高斯消
From： https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day3_A.html