算法

(数学期望,动态规划,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)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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()
{
    scanf("%d%d%d%d", &n, &m, &V, &E);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lf", &p[i]);

    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= V; i ++ ) d[i][i] = d[0][i] = 0;

    for (int i = 0; i < E; i ++ )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        d[u][v] = d[v][u] = min(d[u][v], w);
    }

    for (int k = 1; k <= V; k ++ )
        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 ++ )
        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]));

    printf("%.2lf\n", res);
    return 0;
}