算法

(数学期望,动态规划,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;
}