记得某dalao立了"联赛要是考概率期望我直播吃键盘"的$flag$然后就有了这道题233333
记得考场上不懂概率期望的我傻愣了半天然后弃疗w下场之后$lrd$说这题是$SB$ $DP$感觉整个人都蒟蒻了w我好菜啊
NOIp2016都考概率期望了那以后是不是以后联赛都要FFT辣
这题其实只要明白数学期望的概念以及期望的线性性就可以以明确的思路来做这题了OwO
首先我们使用$Floyd$大法求出所有点对的最短路
设$dp_{i,j,k}$为前$i$门课使用$j$次申请机会,当前科目不申请($k=0$)/申请($k=1$)时的最小期望.然后我们可以分为4种情况转移:第$i-1$门课申请/不申请且第$i$门课申请/不申请($2 \times 2$共4种)
然后分别对前后两节课中的任意一节/两节需要申请的转移分别分两种情况,即申请成功/申请不成功的路径长乘以对应概率求出期望并求和.(所以两节课都要申请的那个表达式巨长OwO)
(可能你本来是明白的但是听了我一番话之后又不明白了QwQ)
结合袋马理解一下吼啦(逃
/******************************
Judge Result:Accepted ******************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <iomanip>
#include <iostream>
#include <algorithm> const int MAXV=;
const int MAXN=;
const double INF=1.0e18; int n;
int m;
int v;
int e;
int c[MAXN];
int d[MAXN];
int dis[MAXV][MAXV];
double ans=INF;
double pr[MAXN];
double dp[MAXN][MAXN][]; void Floyd();
void DynamicProgramming(); int main(){
int a,b,c;
memset(dis,0x3F,sizeof(dis));
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=;i<=n;i++)
scanf("%d",::c+i);
for(int i=;i<=n;i++)
scanf("%d",::d+i);
for(int i=;i<=n;i++)
scanf("%lf",pr+i);
for(int i=;i<e;i++){
scanf("%d%d%d",&a,&b,&c);
dis[a][b]=dis[b][a]=std::min(dis[a][b],c);
}
Floyd();
DynamicProgramming();
printf("%.2lf\n",ans);
} void DynamicProgramming(){
dp[][][]=;
dp[][][]=INF;
for(int i=;i<=n;i++){
dp[i][][]=dp[i-][][]+dis[c[i-]][c[i]];
dp[i][][]=INF;
for(int j=;j<=m;j++){
dp[i][j][]=INF;
dp[i][j][]=INF;
if(dp[i-][j][]!=INF)
dp[i][j][]=std::min(dp[i][j][],dp[i-][j ][]+dis[c[i-]][c[i]]);
if(dp[i-][j-][]!=INF)
dp[i][j][]=std::min(dp[i][j][],dp[i-][j-][]+pr[i ]*dis[c[i-]][d[i]]+(1.0-pr[i ])*dis[c[i-]][c[i]]);
if(dp[i-][j][]!=INF)
dp[i][j][]=std::min(dp[i][j][],dp[i-][j ][]+pr[i-]*dis[d[i-]][c[i]]+(1.0-pr[i-])*dis[c[i-]][c[i]]);
if(dp[i-][j-][]!=INF)
dp[i][j][]=std::min(dp[i][j][],dp[i-][j-][]+pr[i-]*pr[i]*dis[d[i-]][d[i]]+(1.0-pr[i-])*pr[i]*dis[c[i-]][d[i]]+pr[i-]*(1.0-pr[i])*dis[d[i-]][c[i]]+(1.0-pr[i-])*(1.0-pr[i])*dis[c[i-]][c[i]]);
}
}
for(int i=;i<=m;i++)
ans=std::min(ans,std::min(dp[n][i][],dp[n][i][]));
} void Floyd(){
for(int i=;i<=v;i++)
dis[i][i]=;
for(int k=;k<=v;k++){
for(int i=;i<=v;i++){
for(int j=;j<=v;j++){
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
Backup