传送门
一道无脑的期望dp。
用f[i][j][0/1]表示前i堂课提出了j次申请且第i堂课没有（有）提出申请。
这样就可以状态转移了。
然而这题状态转移方程有点长。。。
（主要是情况多。。。
代码：
#include<bits/stdc++.h>
#define N 2005
#define P 305
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,V,E,c[N],d[N];
double dis[P][P],k[N],f[N][N][2];
inline int min(int a,int b){return a<b?a:b;}
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=0;i<=V+1;++i)
for(int j=0;j<=V+1;++j)
if(i!=j)dis[i][j]=1e9;
for(int i=1;i<=E;++i){
int u=read(),v=read();
double w=1.0*read();
dis[u][v]=dis[v][u]=min(dis[u][v],w);
}
for(int kk=1;kk<=V;++kk)
for(int i=1;i<=V;++i)
for(int j=1;j<=V;++j)
dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);
for(int i=2;i<=n;++i){
f[i][0][0]=f[i-1][0][0]+dis[c[i]][c[i-1]];
f[i][0][1]=1e9;
}
f[1][0][1]=f[1][1][0]=1e9;
for(int i=2;i<=n;++i){
for(int j=1;j<=m;++j){
f[i][j][0]=min(f[i-1][j][0]+dis[c[i]][c[i-1]],f[i-1][j][1]+dis[c[i]][d[i-1]]*k[i-1]+dis[c[i]][c[i-1]]*(1-k[i-1]));
f[i][j][1]=f[i-1][j-1][0]+dis[d[i]][c[i-1]]*k[i]+dis[c[i]][c[i-1]]*(1-k[i]);
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+dis[d[i]][c[i-1]]*k[i]*(1-k[i-1])+dis[d[i]][d[i-1]]*k[i]*k[i-1]+dis[c[i]][c[i-1]]*(1-k[i])*(1-k[i-1])+dis[c[i]][d[i-1]]*(1-k[i])*k[i-1]);
}
}
double ans=f[n][0][0];
int up=min(n,m);
for(int i=1;i<=up;++i)ans=min(ans,min(f[n][i][1],f[n][i][0]));
printf("%.2lf",ans);
return 0;
}