题解

思路分析

这是一道经典的期望动态规划问题，核心在于处理申请换教室的概率和最短路的结合。

问题建模

• 牛牛有 $n$ 节课，每节课在教室 $c_i$ 或 $d_i$（申请通过）上
• 申请第 $i$ 节课换教室的成功概率为 $p_i$
• 最多申请 $m$ 节课换教室
• 目标：最小化在教室间移动的期望体力值

解题步骤

1. 预处理最短路

使用 Floyd-Warshall 算法预处理任意两个教室之间的最短距离，时间复杂度 $O(v^3)$。

2. 动态规划求期望

定义状态：$E[i][j][k]$ 表示前 $i$ 节课，已申请 $j$ 次换教室，第 $i$ 节课最终在原教室（$k=0$）或备选教室（$k=1$）上课的最小期望体力值。

3. 状态转移

对于第 $i$ 节课，有两种决策：

• 不申请换教室：必定在 $c_i$ 上课

  • 从 $E[i-1][j][0]$ 转移：$E[i][j][0] = E[i-1][j][0] + G[c_{i-1}][c_i]$
  • 从 $E[i-1][j][1]$ 转移：需要考虑第 $i-1$ 节课申请成功/失败的概率$$E[i][j][0] = \min(E[i][j][0], E[i-1][j][1] + p_{i-1} \cdot G[d_{i-1}][c_i] + (1-p_{i-1}) \cdot G[c_{i-1}][c_i]) $$

• 申请换教室：可能在 $c_i$ 或 $d_i$ 上课

  • 从 $E[i-1][j-1][0]$ 转移到 $E[i][j][1]$：$$E[i][j][1] = E[i-1][j-1][0] + p_i \cdot G[c_{i-1}][d_i] + (1-p_i) \cdot G[c_{i-1}][c_i] $$
  • 从 $E[i-1][j-1][1]$ 转移到 $E[i][j][1]$：需要考虑四种情况（两节课都可能成功/失败）$$E[i][j][1] = E[i-1][j-1][1] + p_{i-1} \cdot p_i \cdot G[d_{i-1}][d_i] + p_{i-1} \cdot (1-p_i) \cdot G[d_{i-1}][c_i] $$$$+ (1-p_{i-1}) \cdot p_i \cdot G[c_{i-1}][d_i] + (1-p_{i-1}) \cdot (1-p_i) \cdot G[c_{i-1}][c_i] $$

4. 边界条件

• $E[1][0][0] = 0$：第1节课不申请，在原教室，无需移动
• $E[1][1][1] = 0$：第1节课申请，无论成功与否，无需移动
• 其余初始化为 $\infty$

5. 答案

$$\text{ans} = \min_{j=0}^{m} \min(E[n][j][0], E[n][j][1]) $$

样例说明

以样例为例：$n=3, m=2$，教室配置：

• 第1节课：$c_1=2, d_1=1$（申请成功率 $p_1=0.8$）
• 第2节课：$c_2=1, d_2=2$（申请成功率 $p_2=0.2$）
• 第3节课：$c_3=2, d_3=1$（申请成功率 $p_3=0.5$）

最短路：$G[1][2]=1, G[2][3]=1, G[1][3]=3$

最优策略：申请第1节和第3节课换教室

• 第1节：可能在教室2或1（概率0.8）
• 第2节：确定在教室1
• 第3节：可能在教室2或1（概率0.5）

期望距离 = $0.8 \times 0 + 0.2 \times 1$ （第1到第2节）$+ 1$（第2到第3节）$= 0.2 + 1.8 = 2.00$

实际答案2.80说明还有其他因素（具体需要完整DP计算）。

复杂度分析

• 时间复杂度：$O(v^3 + nm)$
• 空间复杂度：$O(nm + v^2)$

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
const int M = 310;

int G[M][M], n, m, v, e;
int c[N], d[N];
double E[N][N][2], p[N];

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]);
	}
	memset(G, 0x3f, sizeof G);
	for (int i = 1; i <= e; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u][v] = min(G[u][v], w);
		G[v][u] = min(G[v][u], w);
	}
	for (int i = 1; i <= v; i++) {
		G[i][i] = G[i][0] = G[0][i] = 0;
	}
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			E[i][j][0] = E[i][j][1] = 1e9;
		}
	}
	E[1][0][0] = E[1][1][1] = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= min(i, m); j++) {
			if (j == 0) {
				E[i][j][0] = E[i-1][j][0]+G[c[i-1]][c[i]];
			} else {
				E[i][j][0] = min(E[i][j][0], E[i-1][j][0]+G[c[i-1]][c[i]]);
				E[i][j][0] = min(E[i][j][0], E[i-1][j][1]+p[i-1]*G[d[i-1]][c[i]]+(1.0-p[i-1])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][0]+p[i]*G[c[i-1]][d[i]]+(1-p[i])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][1]+p[i-1]*p[i]*G[d[i-1]][d[i]]+p[i-1]*(1-p[i])*G[d[i-1]][c[i]]+(1-p[i-1])*p[i]*G[c[i-1]][d[i]]+(1-p[i-1])*(1-p[i])*G[c[i-1]][c[i]]);
			}
//			printf("(%.2lf, %.2lf) ", E[i][j][0], E[i][j][1]);
		}
//		printf("\n");
	}
	double rst = 1e9;
	for (int i = 0; i <= m; i++) {
		rst = min(rst, min(E[n][i][0], E[n][i][1]));
	}
	printf("%.2lf", rst);
	
	return 0;
}

题解

思路分析

题目求在提前申请最多 m 节课调换教室的前提下，Bessie 在全部课程之间移动的最小期望距离。核心拆解为：

1. 最短路预处理：教室个数 v ≤ 300，直接使用 Floyd–Warshall 算法得到任意两教室的最短距离 G[x][y]。
2. 动态规划计算期望：设 E[i][j][k] 表示到达第 i 节课时，已经提交了 j 次申请，并且第 i 节课最终在原教室 (k = 0) 或备选教室 (k = 1) 上课时的最小期望移动距离。转移时：
   • 不申请或申请失败：继承上一节的状态并加上对应最短路距离；
   • 申请且成功：根据前一节是否申请成功、当前节是否成功产生四种概率，加权累加距离。

枚举 j 取 min(E[n][j][0], E[n][j][1]) 即可得到答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
const int M = 310;

int G[M][M], n, m, v, e;
int c[N], d[N];
double E[N][N][2], p[N];

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]);
	}
	memset(G, 0x3f, sizeof G);
	for (int i = 1; i <= e; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u][v] = min(G[u][v], w);
		G[v][u] = min(G[v][u], w);
	}
	for (int i = 1; i <= v; i++) {
		G[i][i] = G[i][0] = G[0][i] = 0;
	}
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			E[i][j][0] = E[i][j][1] = 1e9;
		}
	}
	E[1][0][0] = E[1][1][1] = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= min(i, m); j++) {
			if (j == 0) {
				E[i][j][0] = E[i-1][j][0]+G[c[i-1]][c[i]];
			} else {
				E[i][j][0] = min(E[i][j][0], E[i-1][j][0]+G[c[i-1]][c[i]]);
				E[i][j][0] = min(E[i][j][0], E[i-1][j][1]+p[i-1]*G[d[i-1]][c[i]]+(1.0-p[i-1])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][0]+p[i]*G[c[i-1]][d[i]]+(1-p[i])*G[c[i-1]][c[i]]);
				E[i][j][1] = min(E[i][j][1], E[i-1][j-1][1]+p[i-1]*p[i]*G[d[i-1]][d[i]]+p[i-1]*(1-p[i])*G[d[i-1]][c[i]]+(1-p[i-1])*p[i]*G[c[i-1]][d[i]]+(1-p[i-1])*(1-p[i])*G[c[i-1]][c[i]]);
			}
//			printf("(%.2lf, %.2lf) ", E[i][j][0], E[i][j][1]);
		}
//		printf("\n");
	}
	double rst = 1e9;
	for (int i = 0; i <= m; i++) {
		rst = min(rst, min(E[n][i][0], E[n][i][1]));
	}
	printf("%.2lf", rst);
	
	return 0;
}