自动搬运

查看原文

来自洛谷，原作者为

	lemondinosaur 那跑过去的昼夜是孤独的修炼

搬运于2025-08-24 22:32:11，当前版本为作者最后更新于2021-12-18 11:16:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

自然想到设 $dp[i][x][y][z]$ 表示第 $i$ 次服务后三人所在的位置。

易证存在最优方案使得每次服务后三人所在位置互不相同。

考虑到有一个位置肯定为 $a_i$，那么将这一维舍去。

重新设方程就是 $dp[i][x][y]$ 表示第 $i$ 次服务后不在 $a_i$ 位置的剩下两个人所处位置分别为 $x,y$

若由 $dp[i-1][x][y]$ 转移到下一次服务。分三种情况讨论：

如果 $a_{i-1}$ 转移到 $a_i$，那么

$dp[i][x][y]=\min\left\{dp[i-1][x][y]+C[a_{i-1}][a_i]\right\}$

如果 $x$ 转移到 $a_i$，那么

$dp[i][a_{i-1}][y]=\min\left\{dp[i-1][x][y]+C[x][a_i]\right\}$

如果 $y$ 转移到 $a_i$，那么

$dp[i][x][a_{i-1}]=\min\left\{dp[i-1][x][y]+C[y][a_i]\right\}$

第二、三种情况会交换服务员的编号。

那如何输出方案呢？

交换编号和当前的 $x,y$ 都要记录，但是如果内存限制很小那就无能为力了。

如果每一次服务的 $x,y$ 都能知道，那么交换编号就可以正序遍历求出。

再看上面三种情况，第一种 $x,y$ 都没有改变。

第二种 $a_{i-1}$ 改变为 $x$，第三种 $a_{i-1}$ 改变为 $y$。

那么在第二种或第三种情况记录 $x$ 或 $y$。

如果被记录，就把 $a_{i-1}$ 替换成 $x$ 或 $y$。

为什么可以直接替换，因为 $x,y$ 相同不会使答案更优，

所以 $dp[i][a_{i-1}][a_{i-1}]$ 的情况可以被忽略掉。

然后记录下每次 $x,y$ 正序遍历出答案即可。

记录一个编号直接用 unsigned char 即可，内存为 42MB 左右。

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int N=1011,M=211; unsigned char pos[N][M][M];
int m,n,f[2][M][M],res[N],a[N],cost[M][M],X[N],Y[N];
int iut(){
    int ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
int main(){
    m=iut(); n=iut();
    for (int i=1;i<=m;++i)
	for (int j=1;j<=m;++j) cost[i][j]=iut();
    memset(f[0],0x3f,sizeof(f[0]));
    f[0][1][2]=0,a[0]=3,X[0]=1,Y[0]=2;
    for (int i=1;i<=n;++i) a[i]=iut();
    for (int i=1;i<=n;++i){
    	memset(f[i&1],0x3f,sizeof(f[i&1]));
    	for (int j=1;j<=m;++j)
		for (int k=1;k<=m;++k) if (j!=k)
		if (f[(i&1)^1][j][k]<f[0][0][0]){
    	    if (j!=a[i]&&k!=a[i]){
    	 	    int t=f[(i&1)^1][j][k]+cost[a[i-1]][a[i]];
    		    if (f[i&1][j][k]>t)	f[i&1][j][k]=t,pos[i][j][k]=0;
		    }
		    if (a[i-1]!=a[i]&&k!=a[i]){
		    	int t=f[(i&1)^1][j][k]+cost[j][a[i]];
		    	if (f[i&1][a[i-1]][k]>t)
		    		f[i&1][a[i-1]][k]=t,pos[i][a[i-1]][k]=j;
			}
			if (a[i-1]!=a[i]&&j!=a[i]){
				int t=f[(i&1)^1][j][k]+cost[k][a[i]];
				if (f[i&1][j][a[i-1]]>t)
					f[i&1][j][a[i-1]]=t,pos[i][j][a[i-1]]=k;
			}
		}
	}
	int ans=f[0][0][0],mij,mik,F=1,G=2;
	for (int j=1;j<=m;++j)
	for (int k=1;k<=m;++k)
	if (j!=k&&f[n&1][j][k]<ans)
	    ans=f[n&1][j][k],mij=j,mik=k;
	printf("%d\n",ans);
	for (int i=n;i>=1;--i){
		int t=pos[i][mij][mik]; X[i]=mij,Y[i]=mik;
		if (t) (mik==a[i-1])?(mik=t):(mij=t);
	}
	for (int i=1;i<=n;++i){
		if (X[i]==a[i-1]) F=6-F-G;
		    else if (Y[i]==a[i-1]) G=6-F-G;
		printf("%d ",6-F-G);
	}
    return 0;
}