【题解】LuoGu1850：换教室

原题传送门
期望dp
状态：$d{p}_{i,j,0/1}$表示到第$i$个时间点，共计请求$j$次，当前这一个时间点是否请求的答案
预处理：$v<=300$直接$floyd$预处理最短路
转移：
$d{p}_{i,j,0}=min(d{p}_{i-1,j,0}+w_{c_{i-1},c_i},d{p}_{i-1,j,1}+w_{c_{i-1},c_i}\ast (1-k_{i-1})+w_{d_{i-1},c_i}\ast k_i)$
$d{p}_{i,j,1}=min(d{p}_{i-1,j-1,0}+w_{c_{i-1},c_i}\ast (1-k_i)+w_{c_{i-1},d_i}\ast k_i,d{p}_{i-1,j-1,1}+w_{c_{i-1},c_i}\ast (1-k_{i-1})\ast (1-k_i)+w_{c_{i-1},d_i}\ast (1-k_{i-1})\ast k_i+w_{d_{i-1},c_{i-1}}\ast k_{i-1}\ast (1-k_i)+w_{d_{i-1},d_i}\ast k_{i-1}\ast k_i)$

Code：

#include <bits/stdc++.h>
#define maxn 2010
using namespace std;
double dp[maxn][maxn][2], k[maxn];
int n, m, v, e, c[maxn], d[maxn], w[maxn][maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	n = read(), m = read(), v = read(), e = read();
	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 <= v; ++i)
		for (int j = 1; j <= v; ++j)
			if (i != j) w[i][j] = 1e9;
	for (int i = 1; i <= e; ++i){
		int x = read(), y = read(), z = read();
		w[x][y] = min(w[x][y], z), w[y][x] = w[x][y];
	}
	for (int k = 1; k <= v; ++k)
		for (int i = 1; i <= v; ++i)
			if (i != k)
			for (int j = 1; j <= v; ++j)
				if (j != k && i != j)
					w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= m; ++j) dp[i][j][0] = dp[i][j][1] = 1e9;
	dp[1][0][0] = dp[1][1][1] = 0;
	for (int i = 2; i <= n; ++i){
		dp[i][0][0] = dp[i - 1][0][0] + w[c[i - 1]][c[i]];
		for (int j = 1; j <= min(m, i); ++j){
			int A = c[i - 1], B = d[i - 1], C = c[i], D = d[i];
			dp[i][j][0] = min(dp[i - 1][j][0] + w[A][C], dp[i - 1][j][1] + w[A][C] * (1 - k[i - 1]) + w[B][C] * k[i - 1]),
			dp[i][j][1] = min(dp[i - 1][j - 1][0] + w[A][C] * (1 - k[i]) + w[A][D] * k[i],
			 dp[i - 1][j - 1][1] + w[A][C] * (1 - k[i - 1]) * (1 - k[i]) + w[B][C] * k[i - 1] * (1 - k[i]) + w[A][D] * (1 - k[i - 1]) * k[i] + w[B][D] * k[i - 1] * k[i]);
		}
	}
	double ans = 1e9;
	for (int i = 0; i <= m; ++i) ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
	printf("%.2lf\n", ans);
	return 0;
}