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

const int INF = 1e9;
const double EPS = 1e-9;

double solve_n1() {
    return 0.0;
}

double solve_n2(vector<int>& c, vector<int>& d, vector<double>& k, 
                vector<vector<int>>& dist, int m) {
    double ans = INF;
    
    // 枚举第1节课是否申请，第2节课是否申请
    for (int s1 = 0; s1 <= 1; s1++) {
        for (int s2 = 0; s2 <= 1; s2++) {
            // 申请数量不能超过 m
            if (s1 + s2 > m) continue;
            
            double expect = 0.0;
            
            // 枚举第1节课最终在哪个教室（0表示c1，1表示d1）
            for (int r1 = 0; r1 <= 1; r1++) {
                // 如果没申请，r1 只能是 0
                if (s1 == 0 && r1 == 1) continue;
                // 计算概率
                double p1 = (s1 == 0) ? 1.0 : (r1 == 1 ? k[1] : 1 - k[1]);
                if (p1 < EPS) continue;
                
                int room1 = (r1 == 0) ? c[1] : d[1];
                
                // 枚举第2节课最终在哪个教室
                for (int r2 = 0; r2 <= 1; r2++) {
                    if (s2 == 0 && r2 == 1) continue;
                    double p2 = (s2 == 0) ? 1.0 : (r2 == 1 ? k[2] : 1 - k[2]);
                    if (p2 < EPS) continue;
                    
                    int room2 = (r2 == 0) ? c[2] : d[2];
                    
                    // 体力消耗 = 从教室1到教室2的距离
                    double cost = dist[room1][room2];
                    expect += p1 * p2 * cost;
                }
            }
            
            ans = min(ans, expect);
        }
    }
    
    return ans;
}

int main() {
    int n, m, v, e;
    cin >> n >> m >> v >> e;
    
    vector<int> c(n+1), d(n+1);
    vector<double> k(n+1);
    
    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];
    
    // Floyd 初始化
    vector<vector<int>> dist(v+1, vector<int>(v+1, INF));
    for (int i = 1; i <= v; i++) dist[i][i] = 0;
    
    for (int i = 0; i < e; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        dist[a][b] = min(dist[a][b], w);
        dist[b][a] = min(dist[b][a], w);
    }
    
    // n=1 直接输出 0
    if (n == 1) {
        cout << fixed << setprecision(2) << 0.00 << endl;
        return 0;
    }
    
    // Floyd 求最短路（n>=2 时才需要）
    for (int k = 1; k <= v; k++) {
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // n=2 的情况
    double ans = solve_n2(c, d, k, dist, m);
    
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

算法

###($n^3$) 通过枚举子集进行申请的选择交换教室的确定

#include<bits/stdc++.h>
using namespace std;
const int MAXV=305;
const double INF=1e18;
int n,m,v,e;
int c[25],d[25];
double k[25];
int dist[MAXV][MAXV];
double calc(int mask)
{
    double total=0;
    for(int i=1;i<n;i++)
    {
         //枚举第i节课的实际教室
         //第i节课:如果申请了,实际教室可能是c[i]或d[i]
         //如果没有申请,只有c[i]
         int rootsi[2],cnti;
         double prob_i[2];
         if(mask&(1<<(i-1)))
         {
             rootsi[0]=c[i];
             prob_i[0]=1-k[i];
             rootsi[1]=d[i];
             prob_i[1]=k[i];
             cnti=2;
         }
         else
         {
             rootsi[0]=c[i];
             prob_i[0]=1.0;
             cnti=1;
         }
         //枚举第i+1课的两种可能教室
         int rootsj[2],cntj;
         double prob_j[2];
         if(mask&(1<<i))
         {
            rootsj[0]=c[i+1],prob_j[0]=1-k[i+1];
            rootsj[1]=d[i+1],prob_j[1]=k[i+1];
            cntj=2;
         }
         else
         {
             rootsj[0]=c[i+1],prob_j[0]=1.0;
             cntj=1;
         }
         //计算这一段的期望
         double exp=0;
         for(int a=0;a<cnti;a++)
         {
             for(int b=0;b<cntj;b++)
             {
                 exp+=prob_i[a]*prob_j[b]*dist[rootsi[a]][rootsj[b]];
             }
         }
         total+=exp;
    }
    return total;
}
int main()
{
    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];
    for(int i=1;i<=v;i++)
    {
        for(int j=1;j<=v;j++)
        {
            dist[i][j]=(i==j?0:1e9);
        }
    }
    for(int i=0;i<e;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        dist[a][b]=min(dist[a][b],w);
        dist[b][a]=min(dist[b][a],w);
    }
    for(int k=1;k<=v;k++)
    {
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
                if(dist[i][k]+dist[k][j]<dist[i][j])
                {
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }
    double ans=INF;
    for(int mask=0;mask<(1<<n);mask++)
    {
        int cnt=__builtin_popcount(mask);
        if(cnt>m) continue;
        ans=min(ans,calc(mask));
    }
    cout<<fixed<<setprecision(2)<<ans<<endl;
}

(数学期望,动态规划,floyd) O(nm+V^3)

首先用 Floyd算法 预处理出所有点对之间的最短距离。

状态表示：

• f[i][j][0] 表示前 i 个课程，申请换了 j 次，且最后一次没申请换的最小期望长度
• f[i][j][1] 表示前 i 个课程，申请换了 j 次，且最后一次申请交换的最小期望长度

则 f[i][j][0] 在如下两种情况中取最小值即可：

• 第 i-1 个课程没申请交换，最小期望是 f[i-1][j][0]+d[a[i-1]][a[i]]
• 第 i-1 个课程申请交换，最小期望是 f[i-1][j][1]+d[a[i-1]][a[i]]*(1-p[i-1])+d[b[i-1]][a[i]]*p[i-1]

f[i][j][1] 可以用类似的方式得到。

最后遍历 f[n][j][k] 取最小值就是答案。

时间复杂度

• Floyd预处理的计算量是 O(V^3)。
• DP的状态数量是 2mn，每个状态的计算量是 O(1) 的。

因此总时间复杂度是 O(V^3+nm)。

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=310;
const double INF=1e9;
int n,m,V,E;
int a[N],b[N];
double p[N];
int d[M][M];
double f[N][N][2];
int main()
{
    cin>>n>>m>>V>>E;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=V;i++) d[i][i]=d[0][i]=0;
    for(int i=1;i<=E;i++) //获取边权
    {
        int u,v,w;
        cin>>u>>v>>w;
        d[u][v]=d[v][u]=min(d[u][v],w);
    }
    for(int k=1;k<=V;k++) //floyd处理最短路
    {
        for(int i=1;i<=V;i++)
        {
            for(int j=1;j<=V;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    for(int i=0;i<=n;i++) //double初始化无穷点大 
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                f[i][j][k]=INF;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0; //处理起点
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++ )
        {
            f[i][j][0]=min(f[i-1][j][0]+d[a[i-1]][a[i]], 
                          f[i-1][j][1]+d[a[i-1]][a[i]]*(1-p[i-1])+d[b[i-1]][a[i]]*p[i-1]);
            if(j)
                f[i][j][1]=min(f[i-1][j-1][0]+d[a[i-1]][a[i]]*(1-p[i])+d[a[i-1]][b[i]]*p[i],
                                 f[i-1][j-1][1]+d[a[i-1]][a[i]]*(1-p[i-1])*(1-p[i])
                                                    +d[b[i-1]][a[i]]*p[i-1]*(1-p[i])
                                                    +d[a[i-1]][b[i]]*(1-p[i-1])*p[i]
                                                    +d[b[i-1]][b[i]]*p[i-1]*p[i]);
        }
    }
    double res=INF;
    for(int i=0;i<=m;i++)
    {
        res=min(res,min(f[n][i][0],f[n][i][1]));
    }
    cout<<fixed<<setprecision(2)<<res;
    return 0;
}