DP
$n,m\leq2000$，可以考虑 DP。
状态设计
DP 需要满足最优子结构与无后效性原则，因此 DP 方程里的参数需要能够转移。
设 $dp_{i,j,k\in\lbrace0,1\rbrace }$ 表示处理到第 $i$ 个时间段，申请换了（不是实际换了几个） $j$ 个教室，第 $i$ 个教室是否更换的答案。
状态转移
期望，即每种情况的贡献与其出现概率的乘积之和。
令 $a_{x,y}$ 表示教室 $x$ 到教室 $y$ 的最短路长度，因为节点数 $v\leq300$，可以 Floyed $\mathcal O\left(v^3\right)$ 求出。
对于 $dp_{i,0,0}$，显然有：
\[dp_{i,0,0}=dp_{i-1,0,0}+a_{c_{i-1},c_i}\]因为只有这一种情况，无需乘概率。
对于 $dp_{i,j,0}$，有：
\[\begin{aligned} dp_{i,j,0}&=\min \begin{cases} dp_{i-1,j,0}+a_{c_{i-1},c_i}\\ k_{i-1}(dp_{i-1,j,1}+a_{d_{i-1},c_i})+(1-k_{i-1})(dp_{i-1,j,1}+a_{c_{i-1},c_i}) \end{cases}\\ &=\min \begin{cases} dp_{i-1,j,0}+a_{c_{i-1},c_i}\\ dp_{i-1,j,1}+a_{d_{i-1},c_i}\cdot k_{i-1}+a_{c_{i-1},c_i}(1-k_{i-1}) \end{cases} \end{aligned}\]第一行很好理解，即 $i-1$ 不换，直接转移。
第二行讨论的即 $i-1$ 换没换成功，概率分别为 $k_{i-1},1-k_{i-1}$。
同理，可以得到更加复杂的 $dp_{i,j,1}$：
\[dp_{i,j,1}=\min \begin{cases} dp_{i-1,j-1,0}+a_{c_{i-1},d_i}\cdot k_i+a_{c_{i-1},c_i}(1-k_i)\\ dp_{i-1,j-1,1}+a_{d_{i-1},d_i}\cdot k_{i-1}\cdot k_i+a_{d_{i-1},c_i}\cdot k_{i-1}(1-k_i)+a_{c_{i-1},d_i}(1-k_{i-1})k_i+a_{d_{i-1},d_i}(1-k_{i-1})(1-k_i) \end{cases}\]边界条件
\[dp_{1,0,0}=dp_{1,1,1}=0\]显然。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2000,M=2000,V=300;
constexpr const double Max=1e18;
int n,m,v,e,c[N+1],d[N+1],a[V+1][V+1];
double k[N+1],dp[N+1][M+1][2];
template<typename T>
T min(T a,T b,T c){
return (a<b?(a<c?a:c):(b<c?b:c));
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(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];
}
memset(a,0x3f,sizeof(a));
for(int i=1;i<=e;i++){
int u,v,w;
cin>>u>>v>>w;
a[u][v]=a[v][u]=min(a[u][v],w);
}
for(int k=1;k<=v;k++){
for(int i=1;i<=v;i++){
for(int j=1;j<=v;j++){
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
for(int i=0;i<=v;i++){
a[i][i]=0;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j][0]=dp[i][j][1]=Max;
}
}
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]+a[c[i-1]][c[i]];
for(int j=1;j<=i&&j<=m;j++){
dp[i][j][0]=min(
dp[i-1][j][0]+a[c[i-1]][c[i]],
dp[i-1][j][1]+a[d[i-1]][c[i]]*k[i-1]+a[c[i-1]][c[i]]*(1-k[i-1])
);
dp[i][j][1]=min(
dp[i-1][j-1][0]+a[c[i-1]][d[i]]*k[i]+a[c[i-1]][c[i]]*(1-k[i]),
dp[i-1][j-1][1]+a[d[i-1]][d[i]]*k[i-1]*k[i]+a[d[i-1]][c[i]]*k[i-1]*(1-k[i])+a[c[i-1]][d[i]]*(1-k[i-1])*k[i]+a[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])
);
}
}
double ans=Max;
for(int i=0;i<=m;i++){
ans=min(ans,dp[n][i][0],dp[n][i][1]);
}
cout<<fixed<<setprecision(2)<<ans<<'\n';
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
