NOIP2016提高组.换教室

题目

233. 换教室

算法标签: 期望$dp$, $Floyd$求最短路

思路

因为只能在最开始的时候决定每节课的教室是否更换, 因此每个教室之间的概率是独立的, 也就是说总的期望的最小值可以分步计算, 设计状态$f[i][j][0]$表示前$i$门课程中选择更换了$j$门课程的教室并且当前这门课程的教室未更换的所有方案, $f[i][j][1]$代表更换了当前这门教室的所有方案

状态计算取决于上一步是否更换, 每一门课程更换教室的概率是不同的, 独立计算期望相加

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>

using namespace std;

const int N = 2010, M = 2010, V = 310, E = 90010;
const double INF = 0x3f3f3f3f;

int n, m, v, e;
int a[N], b[N];
double p[N];
int d[V][V];
// 前i门课程选择更换教室的课程数量是j并且第i个课程更换教室的状态是k的所有方案
double f[N][M][2];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> v >> e;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= n; ++i) cin >> p[i];

	memset(d, 0x3f, sizeof d);
	for (int i = 1; i <= v; ++i) d[i][i] = d[0][i] = 0;

	for (int i = 0; i < e; ++i) {
   
		int u, v, w;
		cin >> u >> v >> w;
		d[u][v] = d[v][u] = min(d[u][v], w);
	}

	// 处理两个教室直接的最短距离
	for (int k = 1; k <= v; ++k) {
   
		for (int i = 1; i <= v; ++i) {
   
			for (int j = 1; j <= v; ++j) {
   
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}


	for (int i = 0; i <= n; ++i) {
   
		for (int j = 0; j <= m; ++j) {
   
			for (int k = 0; k <= 1; ++k) {
   
				f[i][j][k] = INF;
			}
		}
	}

	f[1][0][0] = f[1][1][1] = 0;
	for (int i = 2; i <= n; ++i) {
   
		for (int j = 0; j <= m; ++j) {
   
			// 不更换当前教室
			f[i][j][0] = min(f[i - 1][j][0] + d[a[i - 1]][a[i]],
							 f[i - 1][j][1] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) + d[b[i - 1]][a[i]] * p[i - 1]);

			// 选择更换当前教室
			if (j) f[i][j][1] = min(f[i - 1][j - 1][0] + d[a[i - 1]][a[i]] *(1 - p[i]) + d[a[i - 1]][b[i]] * p[i],
									f[i - 1][j - 1][1] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) * (1 - p[i]) +
									d[a[i - 1]][b[i]] * (1 - p[i - 1]) * p[i] +
									d[b[i - 1]][a[i]] * p[i - 1] * (1 - p[i]) +
									d[b[i - 1]][b[i]] * p[i - 1] * p[i]);
		}
	}

	double res = INF;
	for (int i = 0; i <= m; ++i) {
   
		res = min({
   res, f[n][i][0], f[n][i][1]});
	}

	cout << fixed << setprecision(2) << res << "\n";
	return 0;
}