非常好的优化 \(\text{DP}\) 状态表示的题目。
首先可以设 \(dp_{i,x,y,z}\) 表示已经做完了前 \(i\) 个请求，现在的 \(3\) 名服务员分别在 \(x\) 、\(y\) 、\(z\) 处的最小花费。
然而这样做时间和空间都会爆炸。
考虑如何优化。
我们注意到做完第 \(i\) 个请求时一定会有一个服务员停留在 \(p_i\) 处，于是可以压掉一维状态。
所以状态就变成了 \(dp_{i,x,y}\) 表示做完了前 \(i\) 个请求，另外 \(2\) 个服务员分别在 \(x\) 和 \(y\) 处的最小花费。
转移的话，枚举下一个请求是由谁做，加上他的位置与下一个请求的位置之间的花费即可。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 203, maxm = 1003;
int n, m, l, dp[maxm][maxn][maxn], c[maxm][maxm], p[maxm];
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
l = gi(), n = gi();
for (int i = 1; i <= l; i+=1)
{
for (int j = 1; j <= l; j+=1)
{
c[i][j] = gi();
}
}
for (int i = 1; i <= n; i+=1) p[i] = gi();
//dp 初始化
memset(dp, 0x3f, sizeof(dp));
p[0] = 3;
dp[0][1][2] = 0;
for (int i = 0; i < n; i+=1)
{
for (int x = 1; x <= l; x+=1)
{
for (int y = 1; y <= l; y+=1)
{
int z = p[i], nxt = p[i + 1];
if (x == y || x == z || y == z) continue;
dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y] + c[z][nxt]); //z 去做
dp[i + 1][z][y] = min(dp[i + 1][z][y], dp[i][x][y] + c[x][nxt]); //x 去做
dp[i + 1][x][z] = min(dp[i + 1][x][z], dp[i][x][y] + c[y][nxt]); //y 去做
}
}
}
int ans = 1000000003;
for (int x = 1; x <= l; x+=1)
{
for (int y = 1; y <= l; y+=1)
{
int z = p[n];
if (x == y || y == z || z == x) continue;
ans = min(ans, dp[n][x][y]);
}
}
printf("%d\n", ans);
return 0;
}