Codeforces 662C. Binary Table(DP)

Author Avatar
Sakits 6月 12, 2018

题解

  很久没有见到这么喵喵的DP了
  首先暴力做法就是枚举每一行的翻转状态,然后暴力扫一次计算答案,复杂度O(m2n)O(m2^n)
  但是可以发现对于枚举的某一个翻转状态,翻转后那些11的个数相同的列可以看作是本质相同的,所以问题转化成了求fi,jf_{i,j}表示与jj异或后11的个数为ii的列有几个,这个可以用一个喵喵DP做到,(据题解说)是个子集反演。
  设dpi,j,kdp_{i,j,k}表示前ii位,与kk异或后有jj11,并且i+1ni+1\sim n位与kk相同的数的个数,则有:

dpi,j,k=dpi1,j,k+dpi1,j1,j xor 2idp_{i, j, k}=dp_{i-1, j, k}+dp_{i-1, j-1, j\ xor\ {2^i}}

  转移表示这一位与kk相同或者这一位与kk11
  然后统计答案显然就是乘上一个min(j,nj)min(j, n-j)了。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=500010;
const ll inf=1e9;
int n, m;
int mp[21][maxn];
ll f[21][1<<20];
char s[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

int main()
{
	read(n); read(m);
	for(int i=1;i<=n;i++) 
	{
		scanf("%s", s+1);
		for(int j=1;j<=m;j++) mp[i][j]=(s[j]=='1');
	}
	for(int j=1;j<=m;j++)
	{
		int tmp=0;
		for(int i=1;i<=n;i++)
		tmp=(tmp<<1)|mp[i][j];
		f[0][tmp]++;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=n;j;j--)
		{
			for(int k=0;k<(1<<n);k++)
			f[j][k]+=f[j-1][k^(1<<i)];
		}
	}
	ll ans=inf;
	for(int i=0;i<(1<<n);i++)
	{
		ll tmp=0;
		for(int j=0;j<=n;j++)
		tmp=(tmp+f[j][i]*min(j, n-j));
		ans=min(ans, tmp);
	}
	printf("%lld\n", ans);
}