自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 21:35:41，当前版本为作者最后更新于2019-09-22 12:38:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本人太弱，不会DP，于是就有了这个只用DFS的题解

首先，我们会想到暴力做法，时间复杂度约为O(C(n,r)C(m,c)rc)，可以得到60分，代码就不提供了

暴力做法之所以慢，是因为进行了重复的计算，而且缺少剪枝。

矩阵的分值包含两部分，一是同一行两个数差的绝对值，二是同一列两个数差的绝对值。如果我们先搜索行再搜索列，第二种分值就可以在搜索行时计算，而第一种分值在搜索列时边搜索边计算。

我们还可以加上搜索常用的最优性剪枝，就是当此时矩阵的分值已经大于等于当前最优答案，那么就退出搜索

代码如下：

void dfsl(ci&x,ci&y,ci&z){//const类型传参，卡常数必备，x为上一列，y为已搜索的列数，z为当前答案
	if(y==c){
		s=z;//更新答案
		return;
	}
	register int i=x+1,en=y+m-c+2,j,zz;//register类型卡常数，en为搜索终止位置
	for(;i<en;++i){
		zz=z+p[i];//p数组存储第二种分值
		if(zz>=s)continue;//剪枝
		if(x!=0){
			for(j=0;j<r;++j){
				zz+=abs(v[e[j]][i]-v[e[j]][x]);//累加第一种分值
			}
		}
		if(zz<s)dfsl(i,y+1,zz);
	}
}
void dfsh(ci&x,ci&y){//搜索行
	if(y==r){
		dfsl(0,0,0);//搜完则搜索列
		return;
	}
	register int i=x+1,en=y+n-r+2,j,q[19];//q数组必须在dfsh函数内定义，用于回溯
	for(;i<en;++i){
		if(x!=0){
			for(j=1;j<=m;++j){
				q[j]=abs(v[x][j]-v[i][j]),p[j]+=q[j];
			}
		}
		e[y]=i,dfsh(i,y+1);//e数组保存取出的行
		if(x!=0){
			for(j=1;j<=m;++j)p[j]-=q[j];//回溯
		}
	}
}

80分，超时，需要继续优化

我们会发现abs进行调用的次数很多，因此可以预处理所有分值，减少重复计算

代码如下：

for(i=1;i<n;++i){//预处理第二种分值
		for(j=i+1;j<=n;++j){
			for(k=1;k<=m;++k){
				g[i][j][k]=abs(v[i][k]-v[j][k]);
			}
		}
	}
	for(i=1;i<m;++i){//预处理第一种分值
		for(j=i+1;j<=m;++j){
			for(k=1;k<=n;++k){
				h[i][j][k]=abs(v[k][i]-v[k][j]);
			}
		}
	}

同时相应修改DFS函数：

void dfsl(ci&x,ci&y,ci&z){
	if(y==c){
		s=z;
		return;
	}
	register int i=x+1,en=y+m-c+2,j,zz;
	for(;i<en;++i){
		zz=z+p[i];
		if(zz>=s)continue;
		if(x!=0){
			for(j=0;j<r;++j){
				zz+=h[x][i][e[j]];//累加第一种分值
			}
		}
		if(zz<s)dfsl(i,y+1,zz);
	}
}
void dfsh(ci&x,ci&y){
	if(y==r){
		dfsl(0,0,0);
		return;
	}
	register int i=x+1,en=y+n-r+2,j;
	for(;i<en;++i){
		if(x!=0){
			for(j=1;j<=m;++j){
				p[j]+=g[x][i][j];//第二种分值
			}
		}
		e[y]=i,dfsh(i,y+1);
		if(x!=0){
			for(j=1;j<=m;++j)p[j]-=g[x][i][j];//回溯
		}
	}
}

依然是80分，但是速度相比之前略快，需要继续剪枝

我们可以考虑将累加第一种分值在dfsh函数中进行，因为dfsh调用次数少于dfsl，因此可以减少重复计算

代码如下：

void dfsl(ci&x,ci&y,ci&z){
	if(y==c){
		s=z;
		return;
	}
	register int i=x+1,en=y+m-c+2,j,zz;
	for(;i<en;++i){
		zz=z+p[i]+w[x][i];//可以一次性求出两种分值之和
		if(zz<s)dfsl(i,y+1,zz);
	}
}
void dfsh(ci&x,ci&y){
	if(y==r){
		dfsl(0,0,0);
		return;
	}
	register int i=x+1,en=y+n-r+2,j,k;
	for(;i<en;++i){
		if(x!=0){
			for(j=1;j<=m;++j){
				p[j]+=g[x][i][j];
			}
		}
		for(j=1;j<m;++j){
			for(k=j+1;k<=m;++k){
				w[j][k]+=h[j][k][i];//用w数组保存第一种分值
			}
		}
		e[y]=i,dfsh(i,y+1);
		if(x!=0){
			for(j=1;j<=m;++j)p[j]-=g[x][i][j];
		}
		for(j=1;j<m;++j){
			for(k=j+1;k<=m;++k){
				w[j][k]-=h[j][k][i];//注意w数组也要回溯
			}
		}
	}
}

这样就可以得到100分了