[学习笔记] 概率与期望及其应用

4.1.1 题目大意

给一张 \(n\) 个点 \(m\) 条边的有向图，每条边有边权。现从 \(1\) 走到 \(n\)，每次等概率选取一条边走，求路径总长度的期望。

4.1.2 思路

考虑进行期望DP。

设 \(f_i\) 表示从点 \(i\) 出发走到点 \(n\) 的期望路径长度，答案即为 \(f_1\)。初始状态 \(f_n=0\)。

反向连边建图，在图上跑拓扑进行转移。

具体地讲，每次取出一个入度为零的点 \(x\)，枚举它能到的点 \(v\)，在正常拓扑的同时转移，转移式为 \(f_v=\frac{f_x+w(x,v)} {deg_v}\)。

4.1.3 代码实现

int n, m;
int last[N], cnt;
struct edge {
	int to, next, w;
} e[N << 1];
void addedge(int x, int y, int w) {
	e[++cnt].to = y;
	e[cnt].next = last[x];
	e[cnt].w = w;
	last[x] = cnt;
}
int deg[N], lne[N]; //deg为拓扑所用的入度数, lne为出边数 
queue  s;
double f[N];
void topsort() {
	for (int i = 1; i <= n; i++)
		if (deg[i] == 0) s.push(i);
	while (s.size()) {
		int x = s.front(); s.pop();
		for (int i = last[x]; i; i = e[i].next) {
			int v = e[i].to; deg[v]--;
			f[v] += (f[x] + e[i].w) * 1.0 / lne[v];
			if (!deg[v]) s.push(v);
		}
	}
}
int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read(), w = read();
		addedge(v, u, w); deg[u]++, lne[u]++; //反向建边 
	}
	topsort();
	printf("%.2lf", f[1]);
	return 0;
}

4.2 [NOIP2016 提高组] 换教室

https://www.luogu.com.cn/problem/P1850

4.2.1 题目大意

一共有 \(n\) 个时间节点上安排了课程，对于每个时间节点 \(i\)，两节内容相同的课会占用 \(c_i\) 和 \(d_i\) 两间教室。

一般来讲，学生需按时间在 \(c_i\) 教室完成第 \(i\) 节课。但他们也可以通过提交申请尝试更换教室。具体地，申请更换第 \(i\) 节课的教室通过的概率为已知实数 \(k_i\)，如果申请通过，学生就可以去 \(d_i\) 教室上课。

牛牛可以提交最多 \(m\) 次申请。由于两教室间的距离和拥堵程度不同，牛牛在前往教室时耗费的体力也不同。当第 \(i(1\leq i 节课结束后，他会从这间教室沿耗费体力最少的路径前往下个教室。

问申请更换教室后 在教室间移动耗费的体力值的总和 的期望值 最小是多少。

4.2.2 思路

需要知道每两间教室直接的最短路长度时多少。这可以用 Floyed 解决。

然后考虑DP，设 \(f_{i,j,0/1}\) 表示前 \(i\) 个时间节点换了 \(j\) 次教室，第 \(i\) 个时间节点 换/没换 教室，耗费的体力值的总和的期望最小是多少。

怎么转移？

\(f_{i,j,0}=\min\{f_{i-1,j,0}+dis(c_{i-1},c_i),f_{i-1,j,1}+dis(d_{i-1},c_i)\times k_{i-1}+dis(c_{i-1},c_i)\times(1-k_{i-1}) \}\)

\(f_{i,j,1}=\min\{f_{i-1,j-1,0}+dis(c_{i-1},d_i)\times k_i+dis(c_{i-1},c_i)\times(1-k_i),\)\(f_{i-1,j-1,1}+dis(d_{i-1},d_i)\times k_{i-1}\times k_i+dis(d_{i-1},c_i)\times k_{i-1}\times(1-k_i)\)\(+dis(c_{i-1},d_i)\times(1-k_{i-1})\times k_i+dis(c_{i-1},c_i)\times(1-k_{i-1})\times(1-k_i) \}\)

答案即为 \(\min_{i=0}^mmin(f_{n,i,0},f_{n,i,1})\)。

4.2.3 代码实现

dp转移太长了，代码很丑，见谅~

const int N = 2010, M = 90010;
const double INF = 1e17;
int n, m, cntroom, cntedge, c[N], d[N];
ll dis[N][N];
double f[N][N][2], k[N];
int main() {
	n = read(), m = read(), cntroom = read(), cntedge = read();
	for (int i = 1; i <= cntroom; i++)
		for (int j = i + 1; j <= cntroom; j++)
			dis[i][j] = dis[j][i] = INF;
	for (int i = 1; i <= n; i++) c[i] = read();
	for (int i = 1; i <= n; i++) d[i] = read();
	for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
	for (int i = 1; i <= cntedge; i++) {
		int u = read(), v = read(), w = read();
		dis[u][v] = dis[v][u] = min(dis[u][v], w * 1ll);
	}
	for (int p = 1; p <= cntroom; p++)
		for (int i = 1; i <= cntroom; i++)	
			for (int j = 1; j <= cntroom; j++)
				dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			f[i][j][0] = f[i][j][1] = INF;
	f[1][0][0] = f[1][1][1] = 0;
	for (int i = 2; i <= n; i++) f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= min(i, m); j++) {
			f[i][j][0] = min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]));
			f[i][j][1] = min(f[i - 1][j - 1][0] + dis[c[i - 1]][d[i]] * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i]), f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i - 1] * k[i] + dis[d[i - 1]][c[i]]* k[i - 1] * (1 - k[i]) + dis[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]));
		}
	double ans = INF;
	for (int i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
	printf("%.2lf\n", ans);
	return 0;
}

参考资料

蒙提霍尔问题（又称三门问题、山羊汽车问题）的正解是什么？ - 知乎

概率与期望及其应用 - 曹文