AcWing 274 移动服务
题目大意
一个公司有三个移动服务员，最初分别在位置$1, 2, 3$
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从$p$到$q$只有一个员工能移动，且不允许在同样位置又两个员工
花费函数不一定对称，保证$c(p, q) = 0$
给出$N$个请求，位置分别位$p_1 \sim p_N$
公司必须按顺序依次满足所有请求， 且过程中不能去其他额外的位置 ，目标是最小化公司花费，请你帮忙计算这个最小花费。
输入格式
第 $1$ 行有两个整数 $L,N$，其中 $L$ 是位置数量，$N$ 是请求数量，每个位置从 $1$ 到 $L$ 编号。
第 $2$至 $L+1$ 行每行包含 $L$ 个非负整数，为邻接矩阵，保证每个数$<2000$
最后一行包含 $N$个整数，是请求列表。
一开始三个服务员分别在位置 $1，2，3$。
输入样例
输出一个整数，表示最小花费。
数据范围
$3 \le L \le 200$
$ 1 \le N \le 1000 $
样例
Input：
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
Output：
5
题解
这题比较值得注意的思维是，它如果考虑状态怎么被转移过来的，即当一个员工在$t_j$时，考虑如何从$t_0 \sim t_{j-1}$转移过来($t_0$表示初始位置)比较复杂，但如果状态怎么转移走的就容易很多了，即$t_j$在紧接的状态更新时要不站着不动，要不走到$t_{j+1}$
并且三个员工显然是轮换对称的，以此可以设计以下状态$f_{i, j, k}$ 表示三人分别在$p_i, j, k$处时的最佳方案，则下一步可以分为三类
- $p_i \rightarrow p_{i+1}$, 代价为 $f_{i+1, j, k} = f_{i, j, k} + c(p_i, p_{i+1})$
- $j \rightarrow p_{i+1}$, 代价为$f_{i+1, p_i, k} = f_{i, j, k} + c(j, p_{i+1})$
- $k \rightarrow p_{i+1}$, 代价为$f_{i+1, p_i, j} = f_{i, j, k} + c(k, p_{i+1})$
最后遍历 $f_{N, 1 \sim L, 1 \sim L}$找到min即可
参考代码
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
//
// Created by Leo on 2023/2/20.
//
// 用往后推的方法，即不找当前状态如何从以前的状态转移过来，而是考虑当前的状态如何推导到下一个状态
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1010, MaxL = 250;
int cost[MaxL][MaxL], tasks[MaxN];
int L, N, ans, f[MaxN][MaxL][MaxL];
int main() {
cin >> L >> N;
for (int i = 1; i <= L; i++)
for (int j = 1; j <= L; j++)
cin >> cost[i][j];
for (int i = 1; i <= N; i++)
cin >> tasks[i];
memset(f, 0x3f, sizeof(f));
f[0][2][3] = 0;
tasks[0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 1; j <= L; j++) {
for (int k = 1; k <= L; k++) {
int pos = tasks[i];
if (pos == j || pos == k || j == k) continue;
f[i + 1][j][k] = min(f[i + 1][j][k], f[i][j][k] + cost[pos][tasks[i + 1]]);
f[i + 1][pos][k] = min(f[i + 1][pos][k], f[i][j][k] + cost[j][tasks[i + 1]]);
f[i + 1][j][pos] = min(f[i + 1][j][pos], f[i][j][k] + cost[k][tasks[i + 1]]);
}
}
}
ans = 0x3f3f3f3f;
for (int i = 1; i <= L; i++)
for (int j = 1; j <= L; j++)
ans = min(ans, f[N][i][j]);
cout << ans << endl;
return 0;
}
