题目
一道毒瘤概率期望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
然后，终于开始DP啦
用\(f[ i ][ j ][ 0/1 ]\) 示到达前i个教室，申请了j次，第i间教室有没有申请的期望最短长度。
！！！注意，j要从0开始，因为可以一次也不申请！！！
$ f[ i ][ j ][ 0 ] \(可以由\)f[ i ][ j ][ 0 ]\(和\)f[ i ][ j ][ 1 ]$转移过来
\(f[ i ][ j ][ 1 ]\)可以由\(f[ i ][ j - 1 ][ 0 ]\)和\(f[ i ][ 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#include #include 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]