【ACWing】274. 移动服务

题目地址：

https://www.acwing.com/problem/content/276/

一个公司有三个移动服务员，最初分别在位置$1,2,3$处。如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。从$p$到$q$移动一个员工，需要花费$c(p,q)$。这个函数不一定对称，但保证$c(p,p)=0$。给出$N$个请求，请求发生的位置分别为$p_1\sim p_N$。公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。

输入格式：
第$1$行有两个整数$L,N$，其中$L$是位置数量，$N$是请求数量，每个位置从$1$到$L$编号。
第$2$至$L+1$行每行包含$L$个非负整数，第$i+1$行的第$j$个数表示$c(i,j)$，并且它小于$2000$。
最后一行包含$N$个整数，是请求列表。
一开始三个服务员分别在位置$1,2,3$。

输出格式：
输出一个整数$M$，表示最小花费。

数据范围：
$3\le L\le 200$
$1\le N\le 1000$

设第$i$个请求位置为$p[i]$，设$f[k][i][j]$是已经处理完前$k$个请求，并且除了那个处理请求的人，另外两个人分别在$i$和$j$的位置的情况下，取得的最小花费。那么在考虑第$k+1$个请求的时候，可以按这个请求谁去处理来分类。如果是处理上一个请求的那个人继续去处理，则$f[k+1][i][j]$可以用$f[k][i][j]+c[p[i]][p[i+1]]$来更新；也可以是当前位于$i$的这个人去处理，则$f[k+1][p[i]][j]$可以用$f[k][i][j]+c[i][p[i+1]]$；另外一种情况也可以类似讨论。代码如下：

#include 
#include 
using namespace std;

const int N = 1010, M = 210;
int n, m;
int f[N][M][M], g[M][M], p[N];

int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &g[i][j]);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);

  memset(f, 0x3f, sizeof f);
  p[0] = 3;
  f[0][1][2] = 0;
  for (int i = 0; i < n; i++)
    for (int x = 1; x <= m; x++)
      for (int y = 1; y <= m; y++) {
        int z = p[i], u = p[i + 1], v = f[i][x][y];
        if (x == y || x == z || y == z) continue;
        f[i + 1][x][y] = min(f[i + 1][x][y], v + g[z][u]);
        f[i + 1][z][y] = min(f[i + 1][z][y], v + g[x][u]);
        f[i + 1][x][z] = min(f[i + 1][x][z], v + g[y][u]);
      }

  int res = 0x3f3f3f3f;
  for (int x = 1; x <= m; x++)
    for (int y = 1; y <= m; y++) {
      int z = p[n];
      if (x == y || x == z || y == z) continue;
      res = min(res, f[n][x][y]);
    }

  printf("%d\n", res);
}
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

时空复杂度$O(N{L}^2)$。