我们可以简单的想到我们的状态转移方程，f[k][x][y][z] 表示走到 第k个点 ，并且三个人分别在x,y,z的情况下最小的花费
但是仔细观察可以发现，在第i个请求完成时，一定有某个员工位于位置a[i] ，只需要知道阶段i和另外两个员工的位置即可描述一个状态，处于a[i]的员工位置对dp来说是冗余信息
#include<iostream> #include<algorithm> #include<cstring> using namespace std ; const int N = 210, M = 1010 ; int f[M][N][N] ; int w[N][N] ; int n , m ; int a[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 >> a[i] ; memset(f,127,sizeof(f)) ; a[0] = 3 ; f[0][1][2] = 0 ; for(int k = 0 ; k < m ; k ++){ for(int i = 1 ; i <= n ;i ++){ for(int j = 1 ; j <= n ;j ++){ if(i == j || i == a[k] || j == a[k]) continue ; f[k+1][i][j] = min(f[k+1][i][j] , f[k][i][j] + w[a[k]][a[k+1]]) ; f[k+1][a[k]][j] = min(f[k+1][a[k]][j] , f[k][i][j] + w[i][a[k+1]]) ; f[k+1][i][a[k]] = min(f[k+1][i][a[k]] , f[k][i][j] + w[j][a[k+1]]) ; } } } int res = 1e9 ; for(int i = 1 ; i <= n ;i ++){ for(int j = 1 ; j <= n ; j ++){ if(i == j || i == a[m] || j == a[m]) continue ; res = min(res , f[m][i][j]) ; } } cout << res << endl ; }
