题目
一道毒瘤概率期望DP。点这里
首先
对于每个时间段（就是每节课），我们有申请和不申请两种情况。如果不申请的话，一定在(c[ i ])，否则，可能在(c[ i ]),也可能在(d[ i ])。所以我们先预处理一些东西。 先用弗洛伊德处理出最短路（这就不用详细介绍了吧）。我们先考虑相邻的两间教室，如果这两间教室都申请的话，就会有四种情况（①都通过，②都没通过，③第一个通过，④第二个通过）感觉又长又臭。所以我们先处理出两间教室都申请的情况。 用(a[ i ])表示在都申请的前提下从第i个教室走到第i+1个教室的期望长度 (dis[ i ] [ j ])表示从教室i到j的最短路。
情况①的概率为 $ k[ i ] k[ i+1 ] $ ，再乘上路径的长度 (dis[ c[ i ] ][ c[ i+1 ] ])
同理 情况② (1 - k[ i ]) (1 - k[ i+1 ]) dis[ d[ i ] ][ d[ i+1 ] ])
情况③ (k[ i ] (1 - k[ i+1 ]) dis[ c[ i ] ][ d[ i+1 ] ])
情况④$(1 - k[ i ]) k[ i+1 ] * dis[ d[ i ] ][ c[ i+1 ] ] $
所以：
for(int i=1;i<=n;i++)
a[i]=(1-k[i])*(1-k[i+1])*dis[c[i]][c[i+1]]+
k[i]*(1-k[i+1])*dis[d[i]][c[i+1]]+k[i]*k[i+1]*dis[d[i]][d[i+1]]+
(1-k[i])*k[i+1]*dis[c[i]][d[i+1]]
太丑了
然后，继续预处理......
(dp[ i ][ 0/1 ][ 0/1 ]) 表示从第i节课的教室到第i+1节课的教室，第i节课的教室有（1）/没有(0)申请，第i+1个教室有(1)/没有(0)申请的期望长度
然后(dp[ i ][ 1 ][ 1 ])的情况就是刚才的(a[ i ])数组啦
其余情况同理可得，于是就：
for(int i=1;i<n;i++)
{
dp[i][0][0]=dis[c[i]][c[i+1]];
dp[i][1][1]=a[i];
dp[i][0][1]=k[i+1]*dis[c[i]][d[i+1]]+(1-k[i+1])*dis[c[i]][c[i+1]];
dp[i][1][0]=k[i]*dis[d[i]][c[i+1]]+(1-k[i])*dis[c[i]][c[i+1]];
}
然后，终于开始DP啦
用(f[ i ][ j ][ 0/1 ]) 示到达前i个教室，申请了j次，第i间教室有没有申请的期望最短长度。
！！！注意，j要从0开始，因为可以一次也不申请！！！
(f[ i ][ j ][ 0 ])可以由(f[ i - 1 ][ j ][ 0 ])和(f[ i - 1 ][ j ][ 1 ])转移过来
(f[ i ][ j ][ 1 ])可以由(f[ i - 1][ j - 1 ][ 0 ])和(f[ i - 1][ j - 1 ][ 1 ])转移过来
先初始化一下 (f[ i ][ 0 ][ 0 ]) 的情况
于是就得到了：
f[1][1][1]=0; f[1][0][0]=0;
for(int i=2;i<=n;i++)
f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j][0]=min(f[i-1][j][1]+dp[i-1][1][0],f[i-1][j][0]+dp[i-1][0][0]);
f[i][j][1]=min(f[i-1][j-1][1]+dp[i-1][1][1],f[i-1][j-1][0]+dp[i-1][0][1]);
}
}
最后统计答案就行啦,要注意可以申请 0到m次。
for(int i=1;i<=m;i++)
ans=min(ans,min(f[n][i][0],f[n][i][1]));
于是，这道题就做完了！
最后贴上完整版代码（大佬勿喷）：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2005;
const int INF = 27654134;
int n,m,v,e,c[N],d[N],dis[N][N];
double a[N],k[N],f[N][N][2],dp[N][2][2],ans=99999999.9;
//a[i]表示在都申请的前提下从第i个教室走到第i+1个教室的期望长度
// dp[i][0/1][0/1]从第i个教室到第i+1个教室，第i个教室有没有申请，第i+1个教室有没有申请的期望长度
//f[i][j][0/1]表示到达前i个教室，申请了j次，第i间教室有没有申请的期望最短长度
int main()
{
memset(f,0x7f,sizeof(f));
// memset(dis,0x7f,sizeof(dis));
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
dis[i][j]=INF;
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=1;i<=n;i++) cin>>k[i];
int x,y,z;
for(int i=1;i<=e;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(dis[x][y]) dis[x][y]=min(dis[x][y],z),dis[y][x]=min(dis[y][x],z);
else dis[x][y]=z,dis[y][x]=z;
}
for(int i=1;i<=v;i++) dis[i][i]=0;
for(int kk=1;kk<=v;kk++)
{
for(int i=1;i<=v;i++)
{
if(kk==i) continue;
for(int j=1;j<=v;j++)
{
if(kk==j||i==j) continue;
if(dis[i][kk]+dis[kk][j]<dis[i][j])
dis[i][j]=dis[i][kk]+dis[kk][j];
}
}
}
for(int i=1;i<=n;i++)
a[i]=(1-k[i])*(1-k[i+1])*dis[c[i]][c[i+1]]+
k[i]*(1-k[i+1])*dis[d[i]][c[i+1]]+k[i]*k[i+1]*dis[d[i]][d[i+1]]+
(1-k[i])*k[i+1]*dis[c[i]][d[i+1]];
for(int i=1;i<n;i++)
{
dp[i][0][0]=dis[c[i]][c[i+1]];
dp[i][1][1]=a[i];
dp[i][0][1]=k[i+1]*dis[c[i]][d[i+1]]+(1-k[i+1])*dis[c[i]][c[i+1]];
dp[i][1][0]=k[i]*dis[d[i]][c[i+1]]+(1-k[i])*dis[c[i]][c[i+1]];
}
f[1][1][1]=0; f[1][0][0]=0;
for(int i=2;i<=n;i++)
f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j][0]=min(f[i-1][j][1]+dp[i-1][1][0],f[i-1][j][0]+dp[i-1][0][0]);
f[i][j][1]=min(f[i-1][j-1][1]+dp[i-1][1][1],f[i-1][j-1][0]+dp[i-1][0][1]);
}
}
for(int i=0;i<=m;i++)
ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2lf
",ans);
return 0;
}