C++(g++ 7.5.0) 解法, 执行用时: 221ms, 内存消耗: 5652K, 提交时间: 2022-09-23 21:20:12

#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;
}

C++14(g++5.4) 解法, 执行用时: 179ms, 内存消耗: 8804K, 提交时间: 2019-08-18 13:02:49

#include<bits/stdc++.h>
using namespace std;
const int N=20;
const int M=1<<N;
const int INF=0x3f3f3f3f;
int n,m,mx,a[N+2],dp[M+5],b[M+5],now;
char s[N+2];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)
	{
		scanf("%s",s);
		now=0;
		for(int j=0;j<m;++j)
		now=now*2+(s[j]-'0');
		a[i]=now;
	}
	memset(dp,INF,sizeof dp);
	dp[0]=0;
	mx=(1<<n);
	for(int i=1;i<mx;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(i>>j&1)
			{				
				int k=__builtin_popcount((b[i^(1<<j)]|a[j])^b[i^(1<<j)]);
				dp[i]=min(dp[i],k*k+dp[i^(1<<j)]);
				b[i]=b[i^(1<<j)]|a[j];
			}
		}
	}
	printf("%d\n",dp[mx-1]); 
	return 0;
}

C++ 解法, 执行用时: 220ms, 内存消耗: 5628K, 提交时间: 2022-05-12 15:03:29

#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;
			while(add)cnt++,add-=add&-add;
			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;
}