前置知识

前言

既然没人讲与概率有关的知识的话，那就让我来简单介绍一下概率的相关知识吧，这个如果不知道的话这道题还是很难写的。

概率相关

定理 $1$：互补法则

定义：若事件 $A$ 发生的概率为 $P(A)$，则其不发生概率为 $1 - P(A)$。

举例：早上起来有两种选择，吃饭和不吃饭，若吃饭的概率为 $\dfrac{3}{10}$，则有不吃饭的概率为 $1 - \dfrac{3}{10} = \dfrac{7}{10}$。

定理 $2$：加法法则（互斥事件）

定义：若事件 $A_1 \sim A_n \in S$ 且 $A_i \cap A_j=\emptyset \quad \forall i, j\in\{1,2,\dots,n\},\quad i \neq j$。

那么集合中所有事件发生的概率 $P = \sum_{i=1}^n P(A_i)$。

举例：掷一次骰子时，点数大于 $4$ 的概率 $P = P(5) + P(6) = \dfrac{1}{6} + \dfrac{1}{6} = \dfrac{1}{3}$。

定理 $3$：乘法法则（无关事件）

定义：若事件 $A$ 与 $B$ 互相独立，不受影响，那么$P(A \cap B) = P(A) \times P(B)$。

举例：早上吃饭的概率为 $\dfrac{3}{10}$，吃完饭写作业的概率为 $\dfrac{5}{6}$，那么早上吃完饭后去写作业的概率为 $\dfrac{3}{10} \times \dfrac{5}{6} = \dfrac{1}{4}$。

题目

题目大意

牛牛需要在 $n$ 个时间段内完成 $2n$ 节课程，每时间段有两节课程分别安排在教室 $c_i$ 和 $d_i$。牛牛可以申请更换教室，申请通过的概率为 $k_i$，最多申请 $m$ 次。更换教室后，牛牛需要在教室间移动，移动的体力消耗为最短路径的体力值。求最小的体力消耗期望值。

思路

题目类型

我们发现对于每一个时间段 $i$ 的课程，都有选 $c_i$ 和 $d_i$ 两种，我们可以很快想到用动态规划来解决期望概率的问题，而最短路径的话可以用弗洛伊德算法求解，因为本题 $1 \le v \le 300$，那么我们的状态如何设计呢？

状态设计

首先，对于每个时间段是一定要在状态里面的。其次，牛牛对于换教室这个事情其实是不感冒的，可以换或者不换，因此换了多少个教室是一定要在条件里面的。最后，因为我们按时间段向后 dp 的话，当前的 $i$ 时间段是由 $i - 1$ 推出的，但是无法记录上一个时间段到底换没换教室，如果要开个别的东西记录一下就太麻烦，因此就需记录上一个时间段是否换了教室。

所以我们可以这样记录状态，用 $dp_{i,j,k}$ 来表示，在第 $i$ 个时间段内，已经选了 $j$ 间教室更换，$k$ 表示当前的为这个时间段是否更换，$k \in \{0,1\}$。

转移方程（分类讨论）

一：选择不更换当前的教室，再次分类讨论。

由互补法则可知，当前成功更换的概率为 $v_i$，失败的概率即为 $1 - v_i$，而下文的 $2$ 与 $3$ 属于互斥事件，因此用加法法则，将两者的概率加到一起。

1. 前一个教室不做更改，当前期望值即为 $f_{c_{i-1},c_i}$。
2. 前一个教室做更改，且更改成功，当前期望值即为 $v_{i-1} \times f_{d_{i-1},c_i}$。
3. 前一个教室做更改，且更改失败，当前期望值即为 $(1 - v_{i-1}) \times f_{c_{i-1},c_i}$。

总结第一大类的情况，为了求最小值，所以取小，即可得出选择不更换当前教室的转移方程：

$$dp_{i,j,0} \gets \min(dp_{i-1,j,0} + f_{c_{i-1},c_i},dp_{i-1,j,1} + v_{i-1} \times f_{d_{i-1},c{i}} + (1 - v_{i-1}) \times f_{c_{i-1},c_i})$$

二：选择更换当前教室，再次分类讨论

下文的 $1$ 和 $2$ 属于互斥事件，而 $3,4,5,6$ 也属于互斥事件，因此用加法法则，将两者的概率加到一起。而对于 $3,4,5,6$，由乘法法则，则将两次概率相乘。

1. 前一个教室不做更改，且当前教室更改成功，当前期望值即为 $v_i \times f_{c_{i-1},d_i}$
2. 前一个教室不做更改，且当前教室更改失败，当前期望值即为 $(1 - v_i) \times f_{c_{i-1},c_i}$
3. 前一个教室做更改，且前一个更改成功，当前教室更改成功，当前期望值即为 $v_{i-1} \times v_i \times f_{d_{i-1},d_i}$
4. 前一个教室做更改，且前一个更改成功，当前教室更改失败，当前期望值即为 $v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i}$
5. 前一个教室做更改，且前一个更改失败，当前教室更改成功，当前期望值即为 $(1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i}$
6. 前一个教室做更改，且前一个更改失败，当前教室更改失败，当前期望值即为 $(1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i}$

总结第一大类的情况，这里的 $j$ 不要忘记 $-1$，即可得出选择更换当前教室的转移方程：

$$dp_{i,j,1} \gets \min(dp_{i-1,j-1,0} + v_i \times f_{c_{i-1},d_i} + (1 - v_i) \times f_{c_{i-1},c_i},dp_{i-1,j-1,1} + v_{i-1} \times v_i \times f_{d_{i-1},d_i} + v_{i-1} \times (1 - v_i) \times f_{d_{i-1},c_i} + (1 - v_{i-1}) \times v_i \times f_{c_{i-1},d_i} + (1 - v_{i-1}) \times (1 - v_i) \times f_{c_{i-1},c_i})$$

代码

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;

const int MAXN = 2005;
const int MAXV = 305;
double f[MAXV][MAXV];
int n,m,e,v;
int c[MAXN],d[MAXN];
double k[MAXN];
double dp[MAXN][MAXN][2];

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> m >> v >> e;
	for(int i = 1;i <= n;i ++) cin >> c[i];
	for(int i = 1;i <= n;i ++) cin >> d[i];
	for(int i = 1;i <= n;i ++) cin >> k[i];
	for(int i = 1;i <= v;i ++){
		for(int j = 1;j <= v;j ++){
			f[i][j] = 1e18;
		}
		f[i][i] = 0;
	}
	for(int u,v,w,i = 1;i <= e;i ++){
		cin >> u >> v >> w;
		f[v][u] = f[u][v] = min(f[u][v],w * 1.0);
	}
	for(int t = 1;t <= v;t ++){
		for(int i = 1;i <= v;i ++){
			for(int j = 1;j <= v;j ++){
				if(f[i][t] + f[t][j] < f[i][j]){
					f[i][j] = f[i][t] + f[t][j];
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][1] = dp[i][j][0] = 1e18;
		}
	}
	dp[1][1][1] = dp[1][0][0] = 0;
	for(int i = 2;i <= n;i ++){
		for(int j = 0;j <= m;j ++){
			dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],dp[i - 1][j][1] + k[i - 1] * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * f[c[i - 1]][c[i]]);
			if(j > 0) dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * k[i] + f[c[i - 1]][c[i]] * (1 - k[i]),dp[i - 1][j - 1][1] + k[i - 1] * k[i] * f[d[i - 1]][d[i]] + k[i - 1] * (1 - k[i]) * f[d[i - 1]][c[i]] + (1 - k[i - 1]) * k[i] * f[c[i - 1]][d[i]] + (1 - k[i - 1]) * (1 - k[i]) * f[c[i - 1]][c[i]]);
		}
	}
	double ans = 1e18;
	for(int i = 0;i <= m;i ++){
		ans = min(ans,min(dp[n][i][1],dp[n][i][0]));
	}
	cout << fixed << setprecision(2) << ans << '\n';
	return 0;
}

好了，记得在进制转换的时候注意一下就可以了，本题做完可以试试 Bag of mice，也是一个概率 dp。

E40 概率DP 求期望

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int n, m, v, e, c[N], d[N];
double p[N], dis[N][N], f[N][N][2];
int main()
{
	
	scanf("%d%d%d%d", &n, &m, &v, &e);
	for(int i=1;i<=n;i++) scanf("%d", &c[i]);
	for(int i=1;i<=n;i++) scanf("%d", &d[i]);
	for(int i=1;i<=n;i++) scanf("%lf", &p[i]);

	for(int i=1;i<=v;i++)for(int j=1;j<=v;j++) dis[i][j]=(i!=j)?2e9:0; 
	for(int i=1;i<=e;i++){
		int x, y;double c;scanf("%d%d%lf", &x, &y, &c);
		dis[x][y]=dis[y][x]=min(dis[x][y], c);
	}
	
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)
			if(dis[i][k]+dis[k][j]<dis[i][j])
				dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
	
	for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)f[i][j][0]=f[i][j][1]=2e9;
	f[1][0][0]=f[1][1][1]=0;
	
	for(int i=2;i<=n;i++)for(int j=0;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[ c[i-1] ][ c[i] ]*(1-p[i-1])
		                            +dis[ d[i-1] ][ c[i] ]*p[i-1]     );
		if(j>0)
		f[i][j][1]=min( f[i-1][j-1][0]+dis[c[i-1]][c[i]]*(1-p[i])
		                              +dis[c[i-1]][d[i]]*p[i],
		                f[i-1][j-1][1]+
		                dis[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])
		                +dis[c[i-1]][d[i]]*(1-p[i-1])*p[i]
		                +dis[d[i-1]][c[i]]*p[i-1]*(1-p[i])
		                +dis[d[i-1]][d[i]]*p[i-1]*p[i]            );
	}

	double ans=2e9;
	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;
}