洛谷P1850 [NOIP2016 提高组] 换教室（期望dp）

#include <bits/stdc++.h>
using namespace std;
int n, m, v, e;
int c[3005], d[3005];
int f[305][305];
double dp[3005][3005][2];//dp[i][j][k]表示前i步申请更换了j次且当前是否申请更换的答案
double p[3005];
int main() {
	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 >> p[i];
	}
	memset(f, 0x3f, sizeof(f));
	for(int i = 1; i <= e; i++) {
		int ai, bi, ci;
		cin >> ai >> bi >> ci;
		f[ai][bi] = f[bi][ai] = min(ci, f[ai][bi]);//防止重边
	}
	for(int k = 1; k <= v; k++) {
		for(int i = 1; i <= v; i++) {
			for(int j = 1; j <= v; j++) {
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	for(int i = 1; i <= v; i++) {
		f[i][i] = 0;//有可能出现c[i - 1] == c[i] 
	}
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= m; j++) {
			dp[i][j][0] = dp[i][j][1] = 1e18;
		}
	}
	dp[1][0][0] = dp[1][1][1] = 0;
	for(int i = 2; i <= n; i++) {
		int t1 = f[c[i - 1]][c[i]], t2 = f[c[i - 1]][d[i]], 
		t3 = f[d[i - 1]][c[i]], t4 = f[d[i - 1]][d[i]];
		for(int j = 0; j <= min(m, i); j++) {
			dp[i][j][0] = min(dp[i - 1][j][0] + t1, dp[i - 1][j][1] + t3 * p[i - 1] + t1 * (1 - p[i - 1]));//t3 * p[i - 1] + t1 * (1 - p[i - 1])是因为如果选择换教室的话结果不一定  这里每一项只乘了p[i - 1]是因为当前确定不申请换教室
			if(j) {
				dp[i][j][1] = min(dp[i - 1][j - 1][0] + p[i] * t2 + (1 - p[i]) * t1, dp[i - 1][j - 1][1] + (1 - p[i - 1]) * (1 - p[i]) * t1 + (1 - p[i - 1]) * p[i] * t2 + p[i - 1] * (1 - p[i]) * t3 + p[i - 1] * p[i] * t4);
			}
		}
	}
	double ans = 1e18;
	for(int i = 0; i <= m; i++) {
		ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
	}
	printf("%.2lf", ans);
}