【1】题解：P1850 [NOIP 2016 提高组] 换教室【概率 DP】【动态规划】

· · 题解

考虑一个动态规划。设 f_{i,j,0/1} 为前 i 个教室换了 j 个（第 i 个是否换了）的期望最小距离，距离显然可以 Floyd 求。我们发现显然要考虑上一个的状态，转移如下：

  1. 考虑都不换教室，也就是 f_{i-1,j,0}+dis_{c_i,c_{i-1}}\to f_{i,j,0}。
  2. 考虑前一个换这一个不换，也就是 f_{i-1,j,1}+dis_{c_i,d_{i-1}}\times k_{i-1}+dis_{c_i,c_{i-1}}\times(1-k_{i-1})\to f_{i,j,0}。
  3. 考虑这个换前一个不换，也就是 f_{i-1,j-1,0}+dis_{c_i,c_{i-1}}\times(1-k_i)+dis_{d_i,c_{i-1}}\times k_i\to f_{i,j,1}。
  4. 剩下一个也就是都换，这样有四项转移，也就是：
\begin{aligned} f_{i-1,j-1,1}&+dis_{c_i,c_{i-1}}\times(1-k_i)\times(1-k_{i-1}) \\ &+dis_{d_i,c_{i-1}}\times k_i\times(1-k_{i-1}) \\ &+dis_{c_i,d_{i-1}}\times (1-k_i)\times k_{i-1} \\ &+dis_{d_i,d_{i-1}}\times k_i\times k_{i-1} \\ & \to f_{i,j,1} \end{aligned}

代码容易实现，主要难点在于细节。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,m,v,e,c[N],d[N],f[N][N];
double k[N],dp[N][N][2],ans;
int main(){
    ios::sync_with_stdio(0);
    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(f,0x3f,sizeof(f));
    for(int i=1;i<=v;i++)
        f[i][i]=0;
    for(int i=1;i<=e;i++){
        int u,v,w;
        cin>>u>>v>>w;
        f[u][v]=min(f[u][v],w);
        f[v][u]=min(f[v][u],w);
    }
    for(int k=1;k<=v;k++)
        for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[i][j][0]=1e18,
            dp[i][j][1]=1e18;
    dp[1][0][0]=dp[1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][0]=min(
                dp[i-1][j][0]+f[c[i-1]][c[i]],
                dp[i-1][j][1]+f[c[i-1]][c[i]]*(1-k[i-1])+f[d[i-1]][c[i]]*k[i-1]
            );
            if(j)dp[i][j][1]=min(
                dp[i-1][j-1][0]+f[c[i-1]][c[i]]*(1-k[i])+f[c[i-1]][d[i]]*k[i],
                dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-k[i])*(1-k[i-1])+f[d[i-1]][c[i]]*k[i-1]*(1-k[i])+f[c[i-1]][d[i]]*k[i]*(1-k[i-1])+f[d[i-1]][d[i]]*k[i]*k[i-1]
            );
        }
    }
    ans=1e18;
    for(int j=0;j<=m;j++)
        ans=min(min(dp[n][j][0],dp[n][j][1]),ans);
    printf("%.2lf",ans);
    return 0;
}