刷题记录:牛客NC25088Corn Fields

传送门:牛客

题目描述:

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N 
≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. 
Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows 
dislike eating close to each other, so when choosing which squares to plant, he avoids choosing 
squares that are adjacent; no two chosen squares share an edge. He has not yet made the final 
choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to 
choose the squares for planting. He is so open-minded that he considers choosing no squares as a 
valid option! Please help Farmer John determine the number of ways he can choose the squares to 
plant.
输入:
2 3
1 1 1
0 1 0
输出;
9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

一道经典的状压dp题目,此题可以仔细体会

对于这道题,我们可以发现其实每行的合法性状态只跟上下行有关,所以其实我们可以先预处理出每一行的可行状态.我们想一下,对于每一块土地,其实我们只有种和不种两种状态,那么其实我们可以使用二进制串来存储.并且我们有一个显然的要求,那就是我们的相邻的两个二进制数字显然是不能都是为1的,对于这种判断,我们使用check函数进行

int check(int x) {//判断该状态有没有相邻的1
	if(x&(x<<1)) return false;
	return true;
}
1
2
3
4

直接将我的当前数字左移一格即可,上述函数比较了每一位二进制数字和右边是否都是1,这样的话也就比较了每一个数字和相邻数字的关系

有上述函数之后,我们直接枚举每一个状态,不难写出预处理函数:

void init() {//记录一行中合法的状态,此时没有考虑上下行,以及实际土地
	cnt=0;
	for(int i=0;i<(1<<n);i++) {
		if(check(i)) state[++cnt]=i;
	}
}
1
2
3
4
5
6

然后呢,我们还需要判断上述一个个朴素的状态和我们的实际土地情况的关系,因为我们的贫瘠土地是不能种植的,所以当我们此时的土地贫瘠且我们此时的状态又需要我们此时的土地时,显然这种状态就是不行的,所以我们需要判断这种情况.

为了方便起见,我们可以将刚开始给我们的土地情况取一下反,这样的话就很容易判断上述关系了(为什么呢,可以自己手模一下).取反一下之后我们就会发现只要我们的土地情况和我们的状态进行与运算之后仍然有一位数字是1的话就是不行的.我们可以根据这种特性来预处理出第一行符合的状态.

下面来讲一下dp方程,我们可以使用$dp[i][s]$来记录第$i$行使用第$s$中状态时的方案数

那么显然的我们可以直接枚举出上一行的每一个可行的状态,然后与本行的可行的状态进行判断,判断与本行可行的状态是否冲突,也就是对应的列是否都是1,如果可行直接累加即可

对于最终的答案就是最后一行的每一个状态的dp式子的结果即可

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
const int mod=1e8;
int check(int x) {//判断该状态有没有相邻的1
	if(x&(x<<1)) return false;
	return true;
}
int m,n;int cnt;
int col[20];int state[1<<13];
void init() {//记录一行中合法的状态,此时没有考虑上下行,以及实际土地
	cnt=0;
	for(int i=0;i<(1<<n);i++) {
		if(check(i)) state[++cnt]=i;
	}
}
int fit(int a,int b) {//判断状态和此时的实际土地贫瘠情况是否相配
	if(state[a]&col[b]) return false;
	return true;
}
int dp[13][1<<13];
int main() {
	m=read();n=read();
	int num;
	init();
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
			num=read();
			if(num==0) col[i]|=(1<<(n-j));
		}
	}
	for(int i=1;i<=cnt;i++){
		if(fit(i,1)) dp[1][i]=1;
	}
	for(int i=2;i<=m;i++) {
		for(int j=1;j<=cnt;j++) {
			if(!fit(j,i)) continue;
			for(int k=1;k<=cnt;k++) {
				if(!fit(k,i-1)) continue;
				if(state[j]&state[k]) continue;
				dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++) {
		ans=(ans+dp[m][i])%mod;
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74