「Mobile Service」移动服务

形式化题目

有 $L$ 个位置和三名服务员，初始分别站在位置 $1, 2, 3$ 。给出移动代价 $c(i, j)$ （从位置 $i$ 移到 $j$ 的花费， $c(i,i)=0$ ，不一定对称），以及按时间顺序发生的 $N$ 个请求 $p_1, \dots, p_N$ 。

每个请求 $p_t$ 发生时，必须派一名服务员移动到位置 $p_t$ ；任何时刻三名服务员不能同时处于同一位置。求满足所有请求的最小总移动代价。

思路

朴素想法：每一轮从 3 名服务员里选 1 个去处理请求，共 $3^N$ 种方案，逐一计算代价取最小。 $N \le 1000$ ，指数级枚举必然超时。

关键观察 1：请求位置必在三人站位之中。每个请求 $p_t$ 处理完后，一定有一名服务员站在 $p_t$ 。也就是说，处理完前 $t$ 个请求后，三名服务员的站位里必然包含 $p_t$ ；"在哪"这件事只需要再记另外两个人的位置，合法状态规模远小于 $L^3$ 。

关键观察 2：本轮的代价只取决于"派谁去"。处理请求 $p$ 时，三名服务员中必有一人已在 $p$ （他可以原地不动，花费 $0$ ）；选择另外两人中的任意一人（或 $p$ 处的人原地）移动过去。移动者从自己的位置 $x$ 出发，花费 $c(x, p)$ ，其余两人不动。

DP 状态设计：设处理完前 $t$ 个请求后，三名服务员按固定顺序站在 $(x, y, z)$ 的最小花费为 $f_t(x, y, z)$ 。转移时枚举 $p_{t+1}$ 与"派第 $i$ 位服务员"：

f_{t+1}(\dots) = \min_i \left\{ f_t(x, y, z) + c(s_i, p_{t+1}) \right\}

其中新站位是把 $s_i$ 替换成 $p_{t+1}$ 后的三元组。

去重约束：题目规定任意时刻不允许两名服务员位于同一位置。因此当被派者移到 $p$ 后若与另一人撞位，这个转移必须被丢弃（这一点在含 $c(x,y)=0$ 的数据上会显著影响答案，不能省略）。

实现细节：不是所有 $(x, y, z)$ 都可能出现，用字典只保存可达状态； $L \le 200, N \le 1000$ 下可达状态峰值远小于 $L^3$ ，转移总数与标准解法同阶。

样例模拟

以样例（ $L=5$ ，请求 4 2 4 1 5 4 3 2 1）的前 3 步为例，展示状态如何演化（每个状态记为三元组（三名服务员站位），括号里标注本轮新增代价）：

轮次	请求	可达状态 → 最小花费
初始	—	`(1,2,3)` → 0
1	4	`(4,2,3)` → 1；`(1,4,3)` → 2；`(1,2,4)` → 1
2	2	`(4,2,3)` → 2；`(1,4,3)` → 3；`(1,2,4)` → 1；`(2,4,3)` → 2；…
3	4	`(2,4,3)` → 3；`(1,2,4)` → 2；`(4,2,3)` → 3；…

可以看出：每一轮只有"三人中谁去请求位"这一个选择，状态数被"请求位必在站位中"牢牢约束住，不会爆炸。

复杂度

时间： $O(N \times |\text{可达状态}| \times 3)$ ，最坏 $O(NL^2)$ （ $N \le 1000, L \le 200$ ）。
空间： $O(|\text{可达状态}|)$ ，即 $O(L^2)$ 级别。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 快餐店 / 服务员调度：D[b][a] 表示一名服务员站在当前请求位、另两人在 {a, b} 的最小花费。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll INF = 1LL << 50; // 该站位不可达的哨兵

int main() {
    ll l, n;
    if (scanf("%lld %lld", &l, &n) != 2) return 0; // 空输入安全返回

    std::vector<std::vector<ll> > cost(l, std::vector<ll>(l));
    for (ll i = 0; i < l; i++) {
        for (ll j = 0; j < l; j++) {
            scanf("%lld", &cost[i][j]);
        }
    }
    std::vector<ll> req(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &req[i]);
    }

    ll p = 3; // 初始视为第 0 个请求发生在 3
    ll big = INF * 2;
    std::vector<std::vector<ll> > D(l, std::vector<ll>(l, big));
    D[0][1] = D[1][0] = 0;

    std::vector<std::vector<ll> > nD(l, std::vector<ll>(l));
    std::vector<ll> ca(l);

    for (ll t = 0; t < n; t++) {
        ll q = req[t];
        ll q1 = q - 1;
        if (q == p) continue; // 唯一合法动作是 p 处服务员原地接单，状态不变
        ll p1 = p - 1;
        ll cp = cost[p1][q1];
        for (ll i = 0; i < l; i++) ca[i] = cost[i][q1];

        // 转移一：p 处服务员去 q，另两人不动 → 新的「另两人」还是 {a, b}
        for (ll b = 0; b < l; b++) {
            for (ll a = 0; a < l; a++) {
                nD[b][a] = D[b][a] + cp;
            }
        }
        for (ll a = 0; a < l; a++) nD[q1][a] = big; // 新请求位上恰有一人
        for (ll b = 0; b < l; b++) nD[b][q1] = big;

        // 转移二：a 去接 q，b 与 p 处服务员留下 → 新的「另两人」是 {b, p}
        for (ll b = 0; b < l; b++) {
            if (b == q1) continue; // b == q 时该动作非法
            ll best = big;
            for (ll a = 0; a < l; a++) {
                ll cand = D[b][a] + ca[a];
                if (cand < best) best = cand;
            }
            if (best < nD[b][p1]) {
                nD[b][p1] = best;
                nD[p1][b] = best;
            }
        }

        // 转移三：q 恰是另两人之一时，只有他原地接单（代价 0）→ 新的「另两人」是 {x, p}
        for (ll x = 0; x < l; x++) {
            ll val = D[x][q1];
            if (val < nD[x][p1]) {
                nD[x][p1] = val;
                nD[p1][x] = val;
            }
        }

        D.swap(nD);
        p = q;
    }

    ll ans = big;
    for (ll b = 0; b < l; b++) {
        for (ll a = 0; a < l; a++) {
            if (D[b][a] < ans) ans = D[b][a];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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
67
68
69#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 19:22
# update_at: 2026-10-01 20:05

import sys
from operator import add

INF = 1 << 50  # "该站位不可达"的哨兵，加法不溢出即可


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    l = next(data)  # 位置数量 L
    n = next(data)  # 请求数量 N

    cost = [[next(data) for _ in range(l)] for _ in range(l)]  # c(i,j)
    req = [next(data) for _ in range(n)]                       # 请求序列 p_1..p_N

    # D[b][a]：一名服务员站在当前请求位 p（本轮前是 3），另两名站在 {a, b} 的最小花费。
    # 对称存储（D[b][a] == D[a][b]），且含 p 下标的格子恒为 INF（另两人不可能在 p）。
    p = 3  # 当前请求位（初始视为第 0 个请求发生在 3）
    big = INF * 2
    D = [[big] * l for _ in range(l)]
    D[0][1] = D[1][0] = 0

    for q in req:
        q1 = q - 1
        if q == p:
            continue  # 唯一合法动作是 p 处服务员原地接单，状态不变

        # ca[a] = c(a, q)：任何人被派去 q 的代价
        ca = [row[q1] for row in cost]
        cp = cost[p - 1][q1]
        p1 = p - 1

        # 转移一：p 处服务员去 q，另两人不动 → 新的"另两人"还是 {a, b}
        nD = [[x + cp for x in D[b]] for b in range(l)]
        nD[q1] = [big] * l          # 新请求位上恰有一人，另两人不能在 q
        for row in nD:
            row[q1] = big

        # 转移二：a 去接 q，b 与 p 处服务员留下 → 新的"另两人"是 {b, p}
        # b == q 时该动作非法（撞位），由转移三单独处理
        for b in range(l):
            if b == q1:
                continue
            best = min(map(add, D[b], ca))
            if best < nD[b][p1]:
                nD[b][p1] = best
                nD[p1][b] = best

        # 转移三：q 恰是另两人之一时，只有他原地接单（代价 0）→ 新的"另两人"是 {x, p}
        for x in range(l):
            v = D[x][q1]
            if v < nD[x][p1]:
                nD[x][p1] = v
                nD[p1][x] = v

        D = nD
        p = q

    print(min(min(row) for row in D))


if __name__ == "__main__":
    solve()

总结

核心是把"服务过第 $t$ 个请求后必有一人在 $p_t$ "变成 DP 状态的一部分，从而把指数枚举压成线性轮数 × 平方级状态。
转移只有 3 个分支（派谁去），代价 $c$ 非对称、 $c(x,x)=0$ 都天然兼容。
去重约束（不允许两名服务员同位）不能丢：在含 $0$ 代价移动的数据上，省略它会得到错误（偏小）的答案。
同样的算法在 C++ 里可以用滚动数组 $f[i][j]$ （另两人位置）落地，复杂度完全一致。