P1850 【换教室】

$\Large\mathcal{Description}$

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

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

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

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

$\Large\mathcal{Solution}$

期望DP。

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

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

先考虑不申请的情况。

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

这样,就可以快乐地DP了!!!

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

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

$\Large\mathcal{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;
}