[noip2016-提高] 换教室

GitHub跳转原题关系图返回列表

通过 Floyd 预处理任意两教室间的最短路，并使用动态规划求出在至多更换 $m$ 节课程限制下，移动消耗体力的期望最小值。

OJ: roj

题目 ID: 3640

难度:提高+/省选-

标签:动态规划概率期望最短路

创建: 2026-10-10 09:20

更新: 2026-10-10 09:20

形式化题目

有 $n$ 节课程依次在 $n$ 个时间段进行，每节课程 $i$ 有两个可能的上课地点：原本安排的教室 $c_i$ 和申请更换后的教室 $d_i$ 。申请成功的概率为 $k_i$ ，不同课程的申请结果互相独立。

你至多可以对 $m$ 节课程提交更换教室的申请，申请一旦提交便不能撤回且不可根据前序结果更改后序决定。两节课程之间如果地点不同，需要移动，教室构成一个包含 $v$ 个顶点、 $e$ 条无向带权边的图。移动消耗体力值为两教室间的最短路径长度。

求在最优的申请策略下，这 $n$ 节课程期间移动所消耗体力的期望值的最小值。

正解

思路

首先由于每次下课后从一间教室走到下一间教室走的必然是最短路径，而且教室数 $v \le 300$ 较小，可以使用 Floyd 算法在 $O(v^3)$ 的时间内求出任意两间教室间的最短路。对于图中的重边保留权值最小的即可。

接下来是一个比较典型的线性动态规划。在所有的 $n$ 节课中依次做出决策（不申请或申请），并且限制了总共最多申请 $m$ 次。由于期望的线性性质，可以按阶段进行转移。我们用 $f[i][j][0/1]$ 表示前 $i$ 节课，共申请了 $j$ 次，第 $i$ 节课 不申请(0) / 申请(1) 时，前 $i$ 节课产生的总移动体力期望的最小值。

可以利用滚动数组优化掉第一维 $i$ ，或者直接每一轮只从上一轮的状态进行转移。设前一节课的原教室为 $c_{prev}$ ，更换后的教室为 $d_{prev}$ ，当前课程原教室为 $c_{curr}$ ，更换后教室为 $d_{curr}$ 。上一节课的成功概率为 $k_{prev}$ ，当前课概率为 $k_{curr}$ 。

若当前课不申请（ $0$ ），那么必然在 $c_{curr}$ 上课：

若上一节课未申请：体力增加为 $dis[c_{prev}][c_{curr}]$
若上一节课申请了：有 $k_{prev}$ 概率在 $d_{prev}$ 上课，有 $(1 - k_{prev})$ 概率仍在 $c_{prev}$ 上课。体力期望增加为 $k_{prev} \times dis[d_{prev}][c_{curr}] + (1 - k_{prev}) \times dis[c_{prev}][c_{curr}]$

若当前课申请（ $1$ ），需要消耗一次申请机会，那么有 $k_{curr}$ 概率在 $d_{curr}$ ，有 $1 - k_{curr}$ 概率仍在 $c_{curr}$ ：

若上一节未申请：体力期望增加为 $k_{curr} \times dis[c_{prev}][d_{curr}] + (1 - k_{curr}) \times dis[c_{prev}][c_{curr}]$
若上一节申请了：有 4 种组合情况，分别为都成功、前成功后失败、前失败后成功、都失败。体力期望增加为： $k_{prev} k_{curr} \times dis[d_{prev}][d_{curr}] + k_{prev} (1 - k_{curr}) \times dis[d_{prev}][c_{curr}] + (1 - k_{prev}) k_{curr} \times dis[c_{prev}][d_{curr}] + (1 - k_{prev}) (1 - k_{curr}) \times dis[c_{prev}][c_{curr}]$

每一轮迭代后保留期望值的最小值即可，由于转移的合法性，初始状态仅 $f[1][0][0] = 0, f[1][1][1] = 0$ （若 $m \ge 1$ ）合法，其余均为无穷大。最后结果即为 $\min(f[n][j][0], f[n][j][1])$ 对 $0 \le j \le m$ 取极小值。

代码

python

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
67import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    n, m, v, e = map(int, data[:4])
    idx = 4
    
    c = [0] + [int(x) for x in data[idx:idx+n]]
    idx += n
    d = [0] + [int(x) for x in data[idx:idx+n]]
    idx += n
    k = [0.0] + [float(x) for x in data[idx:idx+n]]
    idx += n
    
    dis = [[float('inf')] * (v + 1) for _ in range(v + 1)]
    for i in range(1, v + 1):
        dis[i][i] = 0
        
    for _ in range(e):
        u = int(data[idx])
        v_node = int(data[idx+1])
        w = int(data[idx+2])
        idx += 3
        if w < dis[u][v_node]:
            dis[u][v_node] = dis[v_node][u] = w
            
    for p in range(1, v + 1):
        for i in range(1, v + 1):
            if dis[i][p] != float('inf'):
                for j in range(1, v + 1):
                    if dis[i][p] + dis[p][j] < dis[i][j]:
                        dis[i][j] = dis[i][p] + dis[p][j]
                        
    f = [[float('inf')] * 2 for _ in range(m + 1)]
    f[0][0] = 0.0
    if m >= 1:
        f[1][1] = 0.0
        
    for i in range(2, n + 1):
        nf = [[float('inf')] * 2 for _ in range(m + 1)]
        c_prev, d_prev, k_prev = c[i-1], d[i-1], k[i-1]
        c_curr, d_curr, k_curr = c[i], d[i], k[i]
        
        for j in range(min(i, m) + 1):
            v1 = f[j][0] + dis[c_prev][c_curr]
            v2 = f[j][1] + k_prev * dis[d_prev][c_curr] + (1.0 - k_prev) * dis[c_prev][c_curr]
            nf[j][0] = min(v1, v2)
            
            if j > 0:
                v3 = f[j-1][0] + k_curr * dis[c_prev][d_curr] + (1.0 - k_curr) * dis[c_prev][c_curr]
                v4 = f[j-1][1] + \
                     k_prev * k_curr * dis[d_prev][d_curr] + \
                     k_prev * (1.0 - k_curr) * dis[d_prev][c_curr] + \
                     (1.0 - k_prev) * k_curr * dis[c_prev][d_curr] + \
                     (1.0 - k_prev) * (1.0 - k_curr) * dis[c_prev][c_curr]
                nf[j][1] = min(v3, v4)
        f = nf
        
    ans = min(min(f[j][0], f[j][1]) for j in range(m + 1))
    print(f"{ans:.2f}")

if __name__ == '__main__':
    main()

cpp

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long long ll;

const int MAXN = 2005;
const int MAXV = 305;
const double INF = 1e18;

int n, m, v, e;
int c[MAXN], d[MAXN];
double k[MAXN];
int dis[MAXV][MAXV];

double f[MAXN][2];
double nf[MAXN][2];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m >> v >> e)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
    }

    for (int i = 1; i <= v; ++i) {
        for (int j = 1; j <= v; ++j) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = 1e8;
        }
    }

    for (int i = 0; i < e; ++i) {
        int u, v_node, w;
        cin >> u >> v_node >> w;
        if (w < dis[u][v_node]) {
            dis[u][v_node] = w;
            dis[v_node][u] = w;
        }
    }

    for (int p = 1; p <= v; ++p) {
        for (int i = 1; i <= v; ++i) {
            for (int j = 1; j <= v; ++j) {
                if (dis[i][p] + dis[p][j] < dis[i][j]) {
                    dis[i][j] = dis[i][p] + dis[p][j];
                }
            }
        }
    }

    for (int j = 0; j <= m; ++j) {
        f[j][0] = f[j][1] = INF;
    }
    f[0][0] = 0.0;
    if (m >= 1) {
        f[1][1] = 0.0;
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            nf[j][0] = nf[j][1] = INF;
        }
        for (int j = 0; j <= min(i, m); ++j) {
            // 第 i 节课不申请
            double v1 = f[j][0] + dis[c[i-1]][c[i]];
            double v2 = f[j][1] + k[i-1] * dis[d[i-1]][c[i]] + (1.0 - k[i-1]) * dis[c[i-1]][c[i]];
            nf[j][0] = min(v1, v2);
            
            // 第 i 节课申请
            if (j > 0) {
                double v3 = f[j-1][0] + k[i] * dis[c[i-1]][d[i]] + (1.0 - k[i]) * dis[c[i-1]][c[i]];
                double v4 = f[j-1][1] + 
                            k[i-1] * k[i] * dis[d[i-1]][d[i]] + 
                            k[i-1] * (1.0 - k[i]) * dis[d[i-1]][c[i]] + 
                            (1.0 - k[i-1]) * k[i] * dis[c[i-1]][d[i]] + 
                            (1.0 - k[i-1]) * (1.0 - k[i]) * dis[c[i-1]][c[i]];
                nf[j][1] = min(v3, v4);
            }
        }
        for (int j = 0; j <= m; ++j) {
            f[j][0] = nf[j][0];
            f[j][1] = nf[j][1];
        }
    }

    double ans = INF;
    for (int j = 0; j <= m; ++j) {
        ans = min(ans, f[j][0]);
        ans = min(ans, f[j][1]);
    }

    cout << fixed << setprecision(2) << ans << "\n";

    return 0;
}

复杂度

时间复杂度：计算最短路 Floyd $O(v^3)$ 。动态规划状态数为 $O(nm)$ ，每次转移常数时间 $O(1)$ 。故总时间复杂度为 $O(v^3 + nm)$ 。其中 $v \le 300, n,m \le 2000$ ，能够毫无压力地在时限内跑完。
空间复杂度：存储地图最短路 $O(v^2)$ ，DP 使用了滚动数组空间复杂度为 $O(m)$ 或不滚动 $O(nm)$ ，都非常优秀。总空间复杂度为 $O(v^2 + m)$ 。

总结

图中会有重边、自环，需要在建图时对同样两点的距离取最小值。
初始化地图最短距离为无穷大，注意不要使用太大的无穷大造成溢出。DP 的初值同样应为一个较大的数。
概率转移一定要推导仔细，所有概率系数相加恒等于 1，保证期望和正确。输出要注意四舍五入保留两位小数。

★★ 数据目录污染记录（`T78`，数据缺陷第 24 类）

new_ROJ/problems/3640/data/ 原本含 两套互不相同的数据：

序列	数量	首行形态	示例答案	闸门
`classroom1..25.in/.ans`	25 对	`1 1 300 34973`（4 整数 + 多行浮点）	`0.00`	PASS 25/25
★ `problem1..20.in/.ans`	20 对	`1 2` / `1 1`（图的边）	`0`	FAIL 20/20

机械判据（决定性）

原闸门结果 恰好是 PASS=25, FAIL=20：

text

1
2= 「classroom 序列【全过】」+ 「problem 序列【全败】」
⇒ 这不是「算法在 20 个点上错了」，而是【数据分两套】的指纹

★ 判据模式：当失败数恰好等于某个文件序列的长度时，应怀疑「目录里有多个序列」，而不是「算法部分正确」。

处置

★ 不做「让 20 个异题点通过」的努力（那是 T62：不该反解）
异题文件已移出 data/，备份在 new_ROJ/problems/_foreign-3640/（40 个文件）
移出后闸门 PASS=25/25（main.cpp 与 main.py 双通过）⇒ 证实主解对本題序列完全正确

与 `T41` 的关系

编号	缺陷
`T41`	题面与数据是两道不同的题（整个数据都是异题的）
`T78`	★ 数据目录【混入】异题数据（部分污染）

⇒ T78 更隐蔽：一部分点会通过，看起来像「算法不够好」。

题目描述

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$ （ $1 \leq i \leq n$ ）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第 $i$ 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 $i$ 个时间段去教室 $d_i$ 上课，否则仍然在教室 $c_i$ 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $i$ 节课程的教室时，申请被通过的概率是一个已知的实数 $k_i$ ，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 $m$ 门课程，也可以不用完这 $m$ 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 $v$ 个教室，有 $e$ 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 $i$ （ $1 \leq i \leq n-1$ ）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

输入输出格式

输入格式：

第一行四个整数 $n,m,v,e$ 。 $n$ 表示这个学期内的时间段的数量； $m$ 表示牛牛最多可以申请更换多少节课程的教室； $v$ 表示牛牛学校里教室的数量； $e$ 表示牛牛的学校里道路的数量。

第二行 $n$ 个正整数，第 $i$ （ $1 \leq i \leq n$ ）个正整数表示 $c_i$ ，即第 $i$ 个时间段牛牛被安排上课的教室；保证 $1 \le c_i \le v$ 。

第三行 $n$ 个正整数，第 $i$ （ $1 \leq i \leq n$ ）个正整数表示 $d_i$ ，即第 $i$ 个时间段另一间上同样课程的教室；保证 $1 \le d_i \le v$ 。

第四行 $n$ 个实数，第 $i$ （ $1 \leq i \leq n$ ）个实数表示 $k_i$ ，即牛牛申请在第 $i$ 个时间段更换教室获得通过的概率。保证 $0 \le k_i \le 1$ 。

接下来 $e$ 行，每行三个正整数 $a_j, b_j, w_j$ ，表示有一条双向道路连接教室 $a_j, b_j$ ，通过这条道路需要耗费的体力值是 $w_j$ ；保证 $1 \le a_j, b_j \le v$ ， $1 \le w_j \le 100$ 。

保证 $1 \leq n \leq 2000$ ， $0 \leq m \leq 2000$ ， $1 \leq v \leq 300$ ， $0 \leq e \leq 90000$ 。

保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。

保证输入的实数最多包含 $3$ 位小数。

输出格式：

输出一行，包含一个实数，四舍五入精确到小数点后恰好 $2$ 位，表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 $4 \times 10^{-3}$ 。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

输入输出样例

输入样例#1： 复制

3 2 3 3 2 1 2 1 2 1 0.8 0.2 0.5 1 2 5 1 3 3 2 3 1

输出样例#1： 复制

2.80

说明

【样例1说明】

所有可行的申请方案和期望收益如下表:

【提示】

道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是同一间教室。
请注意区分n,m,v,e的意义, n不是教室的数量, m不是道路的数量。

特殊性质1:图上任意两点 $a_i$ , $b_i$ , $a_i$ ≠ $b_i$ 间,存在一条耗费体力最少的路径只包含一条道路。

特殊性质2:对于所有的 $1\leq i\leq n$ ， $k_i= 1$ 。