P1850 [NOIP 2016 提高组] 换教室

知识点

Floyd 最短路 + 概率期望 + 动态规划

题意概括

牛牛每节课原本在教室 $c_i$，可以申请换到教室 $d_i$。第 $i$ 节课申请成功的概率为 $k_i$，最多申请 $m$ 节课。

需要选择申请哪些课程，使相邻课程教室之间最短路长度总和的期望最小。

解题思路

首先，牛牛在两个教室之间一定选择体力消耗最小的路径，因此使用 Floyd 算法求出任意两个教室之间的最短距离。

接下来考虑动态规划。

申请第 $i$ 节课程后，实际上课教室有两种可能：

• 以 $1-k_i$ 的概率在教室 $c_i$；
• 以 $k_i$ 的概率在教室 $d_i$。

相邻两节课之间的期望距离，只和这两节课是否申请有关，与更早的选择无关。因此可以将当前课程是否申请作为状态。

设：

$$f_{j,0}$$

表示处理完当前课程，共申请了 $j$ 节，并且当前课程没有申请时的最小期望体力值。

设：

$$f_{j,1}$$

表示处理完当前课程，共申请了 $j$ 节，并且当前课程申请了时的最小期望体力值。

下面考虑从第 $i-1$ 节课转移到第 $i$ 节课。

当前课程不申请

当前课程一定在教室 $c_i$。

如果上一节课也没有申请，上一节课一定在教室 $c_{i-1}$，新增体力值为：

$$dis(c_{i-1},c_i)$$

对应转移为：

$$f_{j,0}+dis(c_{i-1},c_i)$$

如果上一节课申请了，上一节课有两种可能：

• 以 $1-k_{i-1}$ 的概率在教室 $c_{i-1}$；
• 以 $k_{i-1}$ 的概率在教室 $d_{i-1}$。

新增期望体力值为：

$$(1-k_{i-1})dis(c_{i-1},c_i) +k_{i-1}dis(d_{i-1},c_i) $$

对应转移为：

$$f_{j,1} +(1-k_{i-1})dis(c_{i-1},c_i) +k_{i-1}dis(d_{i-1},c_i) $$

两种情况取最小值。

当前课程申请

当前课程有两种可能：

• 以 $1-k_i$ 的概率在教室 $c_i$；
• 以 $k_i$ 的概率在教室 $d_i$。

如果上一节课没有申请，上一节课一定在教室 $c_{i-1}$，新增期望体力值为：

$$(1-k_i)dis(c_{i-1},c_i) +k_i dis(c_{i-1},d_i)$$

对应转移为：

$$f_{j-1,0} +(1-k_i)dis(c_{i-1},c_i) +k_i dis(c_{i-1},d_i) $$

如果上一节课也申请了，那么相邻两节课分别有两种可能，共有四种组合。

新增期望体力值为：

$$\begin{aligned} &(1-k_{i-1})(1-k_i)dis(c_{i-1},c_i) \\ +{}&(1-k_{i-1})k_i dis(c_{i-1},d_i) \\ +{}&k_{i-1}(1-k_i)dis(d_{i-1},c_i) \\ +{}&k_{i-1}k_i dis(d_{i-1},d_i) \end{aligned} $$

对应转移为：

$$\begin{aligned} f_{j-1,1} &+(1-k_{i-1})(1-k_i)dis(c_{i-1},c_i) \\ &+(1-k_{i-1})k_i dis(c_{i-1},d_i) \\ &+k_{i-1}(1-k_i)dis(d_{i-1},c_i) \\ &+k_{i-1}k_i dis(d_{i-1},d_i) \end{aligned} $$

由于每一层只依赖上一层，可以使用滚动数组将空间复杂度降为 $O(m)$。

最后枚举申请数量 $0$ 到 $m$。题目要求至多申请 $m$ 节，因此答案是所有合法状态的最小值，而不是只计算恰好申请 $m$ 节的情况。

参考代码

/*
题意：最多申请更换 m 节课，每次申请有独立的成功概率，
求相邻课程教室间最短路长度总和的最小期望。

思路：先用 Floyd 求任意教室间最短路。
设 f[j][0/1] 表示处理完当前课程，申请 j 次，
且当前课程不申请或申请时的最小期望。
根据相邻两节课是否申请，计算两种或四种位置组合的期望。
使用滚动数组优化空间。
*/

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=2005;
const int V=305;
const int inf=1e9;
const double INF=1e100;

int c[N],d[N],g[V][V];
double k[N],f[N][2],h[N][2];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m,v,e;
    cin>>n>>m>>v>>e;

    m=min(m,n);

    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];

    for(int i=1;i<=v;i++){
        for(int j=1;j<=v;j++){
            g[i][j]=(i==j?0:inf);
        }
    }

    while(e--){
        int a,b,w;
        cin>>a>>b>>w;

        g[a][b]=min(g[a][b],w);
        g[b][a]=min(g[b][a],w);
    }

    for(int t=1;t<=v;t++){
        for(int i=1;i<=v;i++){
            for(int j=1;j<=v;j++){
                g[i][j]=min(g[i][j],g[i][t]+g[t][j]);
            }
        }
    }

    for(int j=0;j<=m;j++){
        f[j][0]=INF;
        f[j][1]=INF;
    }

    f[0][0]=0;
    if(m) f[1][1]=0;

    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++){
            h[j][0]=INF;
            h[j][1]=INF;
        }

        int up=min(i,m);

        for(int j=0;j<=up;j++){
            h[j][0]=min(
                f[j][0]+g[c[i-1]][c[i]],
                f[j][1]+(1-k[i-1])*g[c[i-1]][c[i]]
                +k[i-1]*g[d[i-1]][c[i]]
            );

            if(!j) continue;

            h[j][1]=min(
                f[j-1][0]+(1-k[i])*g[c[i-1]][c[i]]
                +k[i]*g[c[i-1]][d[i]],

                f[j-1][1]
                +(1-k[i-1])*(1-k[i])*g[c[i-1]][c[i]]
                +(1-k[i-1])*k[i]*g[c[i-1]][d[i]]
                +k[i-1]*(1-k[i])*g[d[i-1]][c[i]]
                +k[i-1]*k[i]*g[d[i-1]][d[i]]
            );
        }

        for(int j=0;j<=m;j++){
            f[j][0]=h[j][0];
            f[j][1]=h[j][1];
        }
    }

    double ans=INF;

    for(int j=0;j<=m;j++){
        ans=min(ans,f[j][0]);
        ans=min(ans,f[j][1]);
    }

    cout<<fixed<<setprecision(2)<<ans<<"\n";

    return 0;
}

复杂度分析

Floyd 最短路的时间复杂度为：

$$O(v^3)$$

动态规划的时间复杂度为：

$$O(nm)$$

总时间复杂度为：

$$O(v^3+nm)$$

空间复杂度为：

$$O(v^2+m)$$