思路分析

个人觉得这个题比前面的简单，不知道为啥标了个mid，简单说下思路，首先很容易想到可以用已经完成请求的数量作为阶段，但是只用这个阶段没有办法描述出一个状态，所以可以想到再添加一些附加信息，那么很明显就是三个人每个人的位置作为附加维度，我们再考虑一下是否有冗余维度的存在，可以发现在完成第i个请求时，p[i] 就是一个人的位置，所以可以看出可以少添加一个维度，至此我们可以写出状态转移方程了

状态表示：

f[i][x][y]表示已经处理完前i个请求，且三个服务员分别在p[i], x, y的所有方案的集合；
f[i][x][y]的值是集合中所有方案的花费的最小值；

状态计算：

这里状态之间的拓扑关系比较特殊，f[i][x][y]所依赖的状态枚举起来不太方便，但f[i][x][y]被依赖的很容易枚举，只有3类：

位于p[i]的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][y] = f[i][x][y] + w[p[i]][p[i + 1]];
位于x的服务员出发前往p[i + 1]，此时状态变成f[i + 1][p[i]][y] = f[i][x][y] + w[x][p[i + 1]];
位于y的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][p[i]] = f[i][x][y] + w[y][p[i + 1]];
最终答案从f[m][1...n][1...n]取最小值即可。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 210, M = 1010;

int w[N][N];
int p[M];
int dp[M][N][N];//当前已经完成了i个请求，剩下俩人在x，y处的最低花费
int n, m;

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j)
            cin >> w[i][j];
    for(int i = 1;i <= m;++i)cin >> p[i];
    memset(dp, 0x3f, sizeof dp);
    p[0] = 3;
    dp[0][1][2] = 0;
    for(int i = 0;i < m;++i)
        for(int x = 0;x <= n;++x)
            for(int y = 0;y <= n;++y){
                int z = p[i], u = p[i+1];
                if(x == y || x == z || y == z)continue;
                //从i推i+1这样好理解
                dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x][y] + w[z][u]);//派z去
                dp[i+1][z][y] = min(dp[i+1][z][y], dp[i][x][y] + w[x][u]);//派x去
                dp[i+1][x][z] = min(dp[i+1][x][z], dp[i][x][y] + w[y][u]);//派y去
            }
    int ans = INT_MAX;
    for(int x = 0;x <= n;++x)
        for(int y = 0;y <= n;++y)
            if(x == y || x == p[m] || y == p[m]) continue;
            else ans = min(ans, dp[m][x][y]);
    cout << ans << endl;
}