题解 | #牛牛的计算机内存#

题意

可以对 $nn$ 条 $0101$ 字符串进行任意排序，排好序后的代价为从前往后每次加入新 $0101$ 串后多出 $11$ 位置数的平方的累加。

解法

本体是经典的状态压缩，状态表示的是m块内存哪些已经访问过了。

用记忆化搜索实现非常方便。函数传递的参数为已经访问过几块内存了、n个位置中哪些位置已经访问过了、当然还有m块内存的状态（如开头所写）。虽然前两者可以通过最后一个计算得到，但是记录下来可以加快程序速度，并且大大减少代码量。

因为只要有最后一个参数我们就能确定一个唯一的状态了，所以记忆化搜索的数组只需要开一维来表示最后一个参数的映射即可。

我来挑战一波最短题解代码

code

#include<bits/stdc++.h>
#define N 21
#define ll long long
using namespace std;

int n,m,a[N],f[1<<N];
bool vst[1<<N];
char c;

ll dfs(int i,ll now,ll k){
	if(i==n)return 0; 
	if(vst[k])return f[k]; vst[k]=true;
	ll res=1e18;
	for(int j=1;j<=n;j++)
		if(!((1<<j-1)&k)){ //如果这块内存还没访问过
			ll add=(now|a[j])^now,cnt=0; //通过按位或算出总共的1，然后用异或去掉本来就是1的位置，算出来的就是新的1
			while(add)cnt++,add-=add&-add; //计算新的1的个数，n&-n表示二进制n最后一个1的大小
			res=min(res,dfs(i+1,now|a[j],(1<<j-1)|k)+cnt*cnt);
		}
	return f[k]=res;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=0;j<m;j++)
			cin>>c,a[i]+=(c-'0')<<j; //将字符串转换为二进制数
	cout<<dfs(0,0,0);
	return 0;
}