P1850 【换教室】

发表于 | 更新于 | 分类于 ，

Description

有 n 个时间段，每个时间段都有两节课，牛牛预先被安排在教室 ci 上课，而另一节课程在教室 di 进行。

牛牛可以申请更换第 i 节课的上课地点(即在教室 di 进行)，申请被通过的概率为 ki。

给定一张带边权无向图，描述教室之间的联通关系。

现要求出在不提交超过 m 次申请(不是申请成功的次数)的情况下，经过边的权值总和的期望的最小值。

Solution

期望DP。

设 F[i][j][1/0] 表示 当前考虑到第 i 个时间段，已经申请了 j 次且第 i 个时间段是否申请的最小期望值。Dis[i][j] 表示 i,j 两个教室之间的最短路。

接着我们尝试列出状态转移方程

先考虑不申请的情况。

F[i][j][0]=min(F[i−1][j][0]+Disci−1,ci,F[i−1][j][1]+ki−1∗Disdi−1,ci+(1−ki−1)∗Disci−1,ci)

同样的，我们也可以写出申请的情况。复杂的一批

F[i][j][1]=min(F[i−1][j−1][0]+ki∗Disci−1,di+(1−ki)∗Disci−1,ci,F[i−1][j−1][1]+ki−1∗ki∗Disdi−1,di+(1−ki−1)∗ki∗Disci−1,di+ki−1∗(1−ki)∗Disdi−1,ci+(1−ki−1)∗(1−ki)∗Disci−1,ci)

这样，就可以快乐地DP了！！！

现在，我们只需要求出 Dis，问题就可以解决了。

我们注意到最多只有 300 个教室，所以直接跑 Floyd 就可以了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 2e3 + 7, M = 305;
const double inf = 1e12;

int Dis[M][M], A[N], B[N];
double F[N][N][2], K[N];

int main() {
    // freopen("a.in", "r", stdin);
    int n, m, v, e;
    read(n), read(m), read(v), read(e);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int i = 1; i <= n; ++i) read(B[i]);
    for (int i = 1; i <= n; ++i) scanf("%lf", &K[i]);
    memset(Dis, 0x3f, sizeof(Dis));
    for (int i = 1; i <= e; ++i) {
        int x, y, k;
        read(x), read(y), read(k);
        if (x == y) continue;
        if (k < Dis[x][y]) Dis[x][y] = Dis[y][x] = k;
    }
    for (int k = 1; k <= v; ++k)
        for (int i = 1; i <= v; ++i) {
            if (i == k) continue;
            int r = Dis[i][k];
            for (int j = 1; j <= v; ++j) {
                if (i == j || j == k) continue;
                Dis[i][j] = std::min(Dis[i][j], r + Dis[k][j]);
            }
        }
    for (int i = 1; i <= v; ++i) Dis[i][i] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j) F[i][j][0] = F[i][j][1] = inf;
    F[1][0][0] = F[1][1][1] = 0;
    for (int i = 2; i <= n; ++i) {
        F[i][0][0] = F[i - 1][0][0] + Dis[A[i - 1]][A[i]];
        for (int j = 1; j <= m; ++j) {
            F[i][j][0] = std::min(F[i - 1][j][0] + Dis[A[i - 1]][A[i]], F[i - 1][j][1] + K[i - 1] * Dis[B[i - 1]][A[i]] + (1 - K[i - 1]) * Dis[A[i - 1]][A[i]]);
            F[i][j][1] = std::min(F[i - 1][j - 1][0] + K[i] * Dis[A[i - 1]][B[i]] + (1 - K[i]) * Dis[A[i - 1]][A[i]], F[i - 1][j - 1][1] + K[i - 1] * K[i] * Dis[B[i - 1]][B[i]] + (1 - K[i - 1]) * K[i] * Dis[A[i - 1]][B[i]] + K[i - 1] * (1 - K[i]) * Dis[B[i - 1]][A[i]] + (1 - K[i - 1]) * (1 - K[i]) * Dis[A[i - 1]][A[i]]);
        }
    }
    double Ans = F[n][0][0];
    for (int i = 1; i <= m; ++i) Ans = std::min(Ans, std::min(F[n][i][0], F[n][i][1]));
    printf("%.2lf\n", 1.0 * (int)(Ans * 100 + 0.5) / 100);
    return 0;
}