rt, 写了一种特别难写的代码，暴力记录三个人的位置，但是转移的时候是 $\mathcal O(n^2)$ 的（枚举另外两个人的位置）。

代码：

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

int l,n;

int c[210][210];

int dp[2][210][210][210]; // dp[i][j][k][l] 表示第 i 个请求的时候三个人分别在哪里

int wz[1010];

int main()
{
	//freopen("1.in","r",stdin);
	//clock_t s=clock();
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>l;
	for(int i=1; i<=l; ++i)
	{
		for(int j=1; j<=l; ++j)
		{
			cin>>c[i][j];
		}
	}
	memset(dp[1],0x3f,sizeof(dp[1]));
	int ans=1e9,i=0;
	cin>>wz[++i];
	for(int k=1; k<=l; ++k)
	{
		for(int kk=1; kk<=l; ++kk)
		{
			if(wz[i]==k || k==kk || wz[i]==kk) continue;
			dp[1][wz[i]][k][kk]=c[1][wz[i]]+c[2][k]+c[3][kk];
			dp[1][k][wz[i]][kk]=c[1][k]+c[2][wz[i]]+c[3][kk];
			dp[1][k][kk][wz[i]]=c[1][k]+c[2][kk]+c[3][wz[i]];
		}
	}
	while(cin>>wz[++i])
	{
		for(int k=1; k<=l; ++k)
		{
			for(int kk=1; kk<=l; ++kk)
			{
				dp[i&1][wz[i]][k][kk]=dp[i&1][k][wz[i]][kk]=dp[i&1][k][kk][wz[i]]=0x3f3f3f3f;
				if(wz[i]==k || k==kk || wz[i]==kk) continue;
				dp[i&1][wz[i]][k][kk]=
				min(dp[i-1&1][wz[i-1]][k][kk]+c[wz[i-1]][wz[i]],
				min(dp[i-1&1][wz[i]][wz[i-1]][kk]+c[wz[i-1]][k],
				dp[i-1&1][wz[i]][k][wz[i-1]]+c[wz[i-1]][kk])),
				dp[i&1][k][wz[i]][kk]=
				min(dp[i-1&1][wz[i-1]][wz[i]][kk]+c[wz[i-1]][k],
				min(dp[i-1&1][k][wz[i-1]][kk]+c[wz[i-1]][wz[i]],
				dp[i-1&1][k][wz[i]][wz[i-1]]+c[wz[i-1]][kk])),
				dp[i&1][k][kk][wz[i]]=
				min(dp[i-1&1][wz[i-1]][kk][wz[i]]+c[wz[i-1]][k],
				min(dp[i-1&1][k][wz[i-1]][wz[i]]+c[wz[i-1]][kk],
				dp[i-1&1][k][kk][wz[i-1]]+c[wz[i-1]][wz[i]]));
			}
		}
	}
	for(int k=1; k<=l; ++k)
	{
		for(int kk=1; kk<=l; ++kk)
		{
			if(wz[i-1]==k || k==kk || wz[i-1]==kk) continue;
			ans=min(ans,min(dp[i-1&1][wz[i-1]][k][kk],min(dp[i-1&1][k][wz[i-1]][kk],dp[i-1&1][k][kk][wz[i-1]])));
		}
	}
	cout<<ans<<'\n';
	//cout<<clock()-s;
	return 0;
}

差 80ms 左右 提交记录

求卡常。

感觉是数组的内存访问慢了，但是不知道如何卡。