跳转至

BZOJ4720 换教室

题解

发现是一个比较简单的期望dp题，一开始想用一个状态f[i][j]表示前i个数取j个的期望，然后用一个数组记录是否申请以帮助转移，后来发现实际上如果某一个状态选择申请，那后面的状态也可能由当前状态的不申请情况转移过来，那也可以比较简单的设计新状态，f[i][j][0/1]，第三位表示当前状态选/不选的期望。

然后就可以用一种简单的方法转移。

1
2
3
4
f[i][j][0] = std::min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1.0 - k[i - 1]));
if (j)
    f[i][j][1] = std::min(f[i - 1][j - 1][0] + k[i] * dis[c[i - 1]][d[i]] + (1.0 - k[i]) * dis[c[i - 1]][c[i]],
                          f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i - 1] * k[i] + dis[d[i - 1]][c[i]] * k[i - 1] * (1.0 - k[i]) + dis[c[i - 1]][d[i]] * (1.0 - k[i - 1]) * k[i] + dis[c[i - 1]][c[i]] * (1.0 - k[i - 1]) * (1.0 - k[i]));

程序

 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
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAX_V 307

int A, B, N, M;
int c[2007], d[2007];
double k[2007], dis[MAX_V][MAX_V], f[2007][2007][2], res = 1e9;

inline int read () {
    int x = 0;
    char c = getchar();
    while (c < '0' || '9' < c)
        c = getchar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x;
}

inline void floyd () {
    for (int i = 1;i <= N; ++i) dis[i][i] = 0;
    for (int k = 1;k <= N; ++k)
        for (int i = 1;i <= N; ++i)
            for (int j = 1;j <= N; ++j)
                if (i != j)
                    dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
}

void dp () {
    for (int i = 1;i <= A; ++i)
        for (int j = 0;j <= B; ++j)
            f[i][j][0] = f[i][j][1] = 1e9;
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2;i <= A; ++i) {
        for (int j = 0;j <= std::min(B, i); ++j) {
            f[i][j][0] = std::min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1.0 - k[i - 1]));
            if (j)
                f[i][j][1] = std::min(f[i - 1][j - 1][0] + k[i] * dis[c[i - 1]][d[i]] + (1.0 - k[i]) * dis[c[i - 1]][c[i]],
                                      f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i - 1] * k[i] + dis[d[i - 1]][c[i]] * k[i - 1] * (1.0 - k[i]) + dis[c[i - 1]][d[i]] * (1.0 - k[i - 1]) * k[i] + dis[c[i - 1]][c[i]] * (1.0 - k[i - 1]) * (1.0 - k[i]));
        }
    }
    for (int i = 0;i <= B; ++i)
        res = std::min(res, std::min(f[A][i][0], f[A][i][1]));
    printf("%.2lf\n", res);
}

int main () {
    A = read(), B = read(), N = read(), M = read();
    for (int i = 1;i <= A; ++i)
        c[i] = read();
    for (int i = 1;i <= A; ++i)
        d[i] = read();
    int u, v;
    double w;
    for (int i = 1;i <= A; ++i)
        scanf("%lf", k + i);
    for (int i = 1;i <= N; ++i)
        for (int j = 1;j <= N; ++j)
            dis[i][j] = 1e9;
    for (int i = 1;i <= M; ++i) {
        u = read(), v = read(), scanf("%lf", &w);
        dis[u][v] = std::min(dis[u][v], w);
        dis[v][u] = dis[u][v];
    }
    floyd();
    dp();
    return 0;
}