题意
一个公司有三个移动服务员，最初分别在位置 1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
这个函数不一定对称，但保证 c(p,p)=0。
给出 N 个请求，请求发生的位置分别为 p1∼pN。
公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。
思路
线性dp：
状态表示：f[i][x][y] 表示已经处理完前 i 个请求 并且服务员在 p[i]、x、y 位置上的所有状态的集合
**属性：**最小值
**状态计算：**由状态 i向 i + 1转移比较方便 有三种情况
这题首先肯定想到 用f[i][x][y][z] 表示状态 但是显然复杂度超了 所以考虑优化掉一维
由于不管怎么走 计算到i+1 时 肯定有一个服务员在 p[i] 所以只要枚举两个服务员的位置即可
不允许两个员工出现在同一个位置 所以要特判一下
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' //#define int long long using namespace std; inline int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } inline int lowbit(int x) { return x & -x; } typedef long long LL; typedef pair<int, int>PII; const int N = 210, M = 1010; int n, m; int w[N][N]; int f[M][N][N]; int p[M]; void solve() { cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%lld", &w[i][j]); for (int i = 1; i <= m; ++i) cin >> p[i]; memset(f, 0x3f, sizeof f); p[0] = 3; f[0][1][2] = 0; for (int i = 0; i < m; ++i) { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { if (x == y || x == p[i] || y == p[i])continue; f[i + 1][x][y] = min(f[i + 1][x][y], f[i][x][y] + w[p[i]][p[i + 1]]); f[i + 1][p[i]][y] = min(f[i + 1][p[i]][y], f[i][x][y] + w[x][p[i + 1]]); f[i + 1][x][p[i]] = min(f[i + 1][x][p[i]], f[i][x][y] + w[y][p[i + 1]]); } } } int res = INF; for (int x = 1; x <= n; ++x) { for (int y = 1; y <= n; ++y) { if (x == y || x == p[m] || y == p[m])continue; res = min(res, f[m][x][y]); } } cout << res << endl; } signed main() { //int t; cin >> t; //while(t--) solve(); return 0; }
