夏晓光(loveJY)的博客

做个D题还这么慢QAQ

首先我们必须猜出一个结论,n>=4时无解

因为n>=4的时候一定存在一个4*4的矩阵

而这个矩阵可以被分成4个2*2的小矩阵

同时每个矩阵都要是奇数个,那么4*4的那个矩阵就一定不能是奇数个了

这个还是很妙的

然后剩下我们就可以状压了...

$dp_{i,S}$表示前i行第i行的状态是S的最少次数

转移的时候预处理相邻状态合法的是那些以及$cnt_i$表示i的二进制位

然后直接做就好了....QAQ

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 15;
const int MAXM = 1e6 + 7;
int n, m;
char s[MAXM];
int vis[MAXN][MAXN];
int a[MAXN][MAXM], tmp[MAXM], dp[MAXM][MAXN], cnt[MAXN];

inline void init() {
	// printf("%d %d\n", n, m);
	for(int S1 = 0; S1 < (1 << n); ++S1) {
		for(int S2 = 0; S2 < (1 << n); ++S2) {
			int tmp1 = 0, tmp2 = 0;
			vis[S1][S2] = 1;
			for(int k = 0; k < n; ++k) {
				tmp2 = (S1 >> k & 1) + (S2 >> k & 1);
				// printf("%d?%d\n", tmp2, tmp1);
				if(k != 0 && ((tmp1 + tmp2) & 1) == 0)
					vis[S1][S2] = 0;
				tmp1 = tmp2;
				tmp2 = 0;
			}
			// printf("%d %d %d?\n", S1, S2, vis[S1][S2]);
		}
	}
	// printf("%d %d\n", n, m);
	for(int S = 0; S < (1 << n); ++S) {
		for(int i = 0; i < n; ++i) {
			if(S & (1 << i))cnt[S]++;
		}
		// printf("%d %d\n", S, cnt[S]);
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	for(int i = 1; i <= m; ++i) {
		// printf("in - >%d?\n", i);
		for(int j = 1; j <= n; ++j) {
			// printf("%d?a :%d\n", j, a[j][i]);
			tmp[i] |= (a[j][i] << (j - 1));
		}
		// printf("%d %d\n", i, tmp[i]);
		// dp[i][tmp[i]] = 0;
	}
	int MAXS = (1 << n) - 1;
	for(int S = MAXS, qwq = 1; S || qwq; S = (S - 1)&MAXS) {
		if(!S)qwq = 0;
		dp[1][S] = cnt[S ^ tmp[1]];
	}
	return;
}

inline void solve() {
	int MAXS = (1 << n) - 1;
	for(int i = 2; i <= m; ++i) {
		for(int S1 = MAXS, qwq = 1; S1 || qwq; S1 = (S1 - 1)&MAXS) {
			if(!S1)qwq = 0;
			for(int S2 = MAXS, qaq = 1; S2 || qaq; S2 = (S2 - 1)&MAXS) {
				if(!S2)qaq = 0;
				// printf("%d?%d?\n", S1, S2);
				if(!vis[S1][S2])continue;
				int qwq = cnt[S1 ^ tmp[i]];
				// printf("we are in->%d? %d? %d\n", S1, S2, i);
				dp[i][S1] = min(dp[i][S1], dp[i - 1][S2] + qwq);
				// printf("qwq is %d dp value is%d and %d\n", qwq, dp[i][S1], dp[i - 1][S2]);
			}
		}
	}
	int ans = 1e9;
	for(int S = 0; S <= MAXS; ++S) {
		ans = min(ans, dp[m][S]);
	}
	if(ans != 1e9)
		printf("%d\n", ans);
	else puts("-1");
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	if(n >= 4 && m >= 4)return puts("-1"), 0;
	if(n <= m) {
		for(int i = 1; i <= n; ++i) {
			scanf("%s", s + 1);
			for(int j = 1; j <= m; ++j) {
				a[i][j] = s[j] - '0';
			}
		}
	} else {
		for(int i = 1; i <= n; ++i) {
			scanf("%s", s + 1);
			for(int j = 1; j <= m; ++j) {
				a[j][i] = s[j] - '0';
			}
		}
		n ^= m ^= n ^= m;
		// for(int i = 1; i <= n; ++i) {
		// 	for(int j = 1; j <= m; ++j) {
		// 		printf("shuchu a:%d %d %d\n", i, j, a[i][j]);
		// 	}
		// }
	}
	init();
	solve();
	return 0;
}