算法

###($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;
}