本篇是从状态压缩到状压DP的过渡篇，也就是这一篇主要讲状态压缩怎么压的。

下面就拿一道例题来分析
题目链接https://vjudge.net/contest/305270#problem/G

---

题目大意：给你n * n的01矩阵，你的任务是把尽量少的0变成1，使得每个元素的上、下，左、右的元素之和均为偶数。

emmm，这就是个比较裸的状态压缩题目，我们枚举第一层的状态，然后筛选出符合条件的情况（即1的位置不能为0），接着按照第一层的状态拓展到第n层，不过为了简化，我们从第0层到第n-1层。

枚举第0层的情况：

for (int i=0; i<(1<<n); i++)

可以看做二进制下的：00000、10000、01000、11000、01100…
筛选：

for (int i=0; i<n; i++) {
	if (s&(1<<i)) b[0][i]=1;
	else if (a[0][i]) return inf;
}

接下来枚举以下的层数：

for (int i=1; i<n; i++) { //row
	for (int j=0; j<n; j++) { //col
		int sum=0;
		if (i>1) sum+=b[i-2][j];
		if (j>0) sum+=b[i-1][j-1];
		if (j<n-1) sum+=b[i-1][j+1];
		b[i][j]=sum&1;
		if (a[i][j]==1 && b[i][j]==0) return inf;
	}
}

即：对i-1行进行计算，然后判断第i行是否为1.

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;
const int inf=999999999;
int a[20][20],b[20][20],n;
int check(int s);
int main()
{
	int t;
	scanf ("%d",&t);
	int cas=0;
	while (cas<t){
		scanf ("%d",&n);
		for (int i=0; i<n; i++)
		 for (int j=0; j<n; j++)
		  scanf ("%d",&a[i][j]);
		int ans=inf;
		for (int i=0; i<(1<<n); i++){
			ans=min(ans,check(i));
		}
		printf ("Case %d: ",++cas);
		if (ans==inf) printf ("-1\n");
		else printf ("%d\n",ans);
	}
	return 0;
}
int check(int s)
{
	memset(b,0,sizeof(b));
	int ans=0;
	for (int i=0; i<n; i++){
		if (s&(1<<i)) b[0][i]=1;
		else if (a[0][i]) return inf;
	}
	for (int i=1; i<n; i++){//row
		for (int j=0; j<n; j++){//col
			int sum=0;
			if (i>1) sum+=b[i-2][j];
			if (j>0) sum+=b[i-1][j-1];
			if (j<n-1) sum+=b[i-1][j+1];
			b[i][j]=sum&1;
			if (a[i][j]==1 && b[i][j]==0) return inf;
		}
	}
	for (int i=0; i<n; i++)
	    for (int j=0; j<n; j++){
	    	if (a[i][j]!=b[i][j]) ans++;
		}
	return ans;
}