POJ 3254 Corn Fields 状压DP

缘起

学习状压DP~ POJ 3254 Corn Fields

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放
牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。现在输入数据给出这块地的大小及可否放
牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！

【输入】
第一行是两个正整数 M和N
1 ≤ M ≤ 12; 1 ≤ N ≤ 12
第二行到第M+1行, 每行N个整数，每个整数不是0就是1. 

【输出】
方案总数, 注意,数量可能很大, 所以输出模掉 1亿的结果.

【样例输入】
2 3
1 1 1
0 1 0

【样例输出】
9

【限制】
2s 64MB

本题也算是状压DP的经典题了。

本题其实和【1】极为相似（但是本题是求方法数, 而【1】是求最大放牧数, 求的东西不同）. 甚至比【1】要简单. 因为【1】中的一个方格的控制范围是一个十字, 十字的臂长是2, 而本题一个方格的控制范围也是一个十字, 而且这个十字的臂长是1. 还小一号~

显然, 如果暴力的话, 本题就是裸的dfs（其实【1】也是）， 因为你不就是每个为1的格子选与不选吗?

But, 本题的数据规模达到了12*12=100+，如果暴力dfs的话, 分分钟炸飞服务器的!

怎么做呢? 和【1】一样, 也是注意到下一行的放牧状态其实和太早的行的放牧状态无关, 而仅仅和它上一行的放牧状态有关, 所以我们完全可以状压一行的状态. 一行的状态通过一个 [0, full:=2^m)的整数刻画就行了. 

1
2
3
4
令 dp[i][j] 是第i行状态为j时的方法数. 则
dp[i][j] = \Sigma_{0<=k<full,而且k和j不冲突}dp[i-1][k], 1<=i<n, 0<=j<full
初始化是 dp[0][j], 0<=j<full, 如果j合法的话, 那dp[0][j]就是j中1的个数, 否则就是0.
最后的答案是 数组dp[n-1]所有元素之和。

其实对比一下【1】就知道为什么【1】中dp的对象需要三维数组, 是因为一行的状态是否合法, 和前两行有关, 同理, 这里因为一行的状态和它前一行有关, 所以这里dp的对象是一个二维数组.

知道了这些, 就可以愉快的切这道题了. 虽然本题显然可以像【1】那样滚动数组, 但是没必要了.

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int MOD = 1e8;
int n,m, a[12][12],dp[1<<12][1<<12], full;

inline int ck(int i, int j)
{
	for (int k = 0; k<m; k++)
	{
		if (j>>k&1 && !a[i][k])
		{
			return 0;
		}
	}
	return 1;
}

int ck_int[1<<12];

inline int ck(int j)
{
	if (~ck_int[j])
	{
		return ck_int[j];
	}
	for (int i = 0,k = -100;i<m;i++)
	{
		if (j>>i&1)
		{
			if (i-k<=1)
			{
				return ck_int[j] = 0;
			}
			k =i;
		}
	}
	return ck_int[j] = 1;
}

inline int lowbit(int j)
{
	return j&-j;
}

int ckk_int_int[1<<12][1<<12];

inline int ckk(int k,int j)
{
	if (~ckk_int_int[k][j])
	{
		return ckk_int_int[k][j];
	}
	for (int i = 0;i<m;i++)
	{
		if ((k>>i&1) && (j>>i&1))
		{
			return ckk_int_int[k][j] = 0;
		}
	}
	return ckk_int_int[k][j] = 1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(ck_int, -1, sizeof(ck_int));
	memset(ckk_int_int, -1, sizeof(ckk_int_int));
	scanf("%d%d", &n,&m);
	for (int i = 0;i<n;i++)
	{
		for (int j = 0;j<m; j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	full = 1<<m;
	for (int j = 0;j<full; j++)
	{
		if (ck(0,j) && ck(j))
		{
			dp[0][j] = 1;
		}
	} // dp初始化
	for (int i = 1;i<n; i++)
	{
		for (int k = 0;k<full;k++) // k是第i-1行的状态
		{
			if (!ck(i-1,k) || !ck(k))
			{
				continue;
			}
			for (int j = 0;j<full; j++) // j是第i行的状态
			{
				if (!ck(i,j) || !ck(j) || !ckk(k,j))
				{
					continue;
				}
				dp[i][j]+=dp[(i-1)][k];
				dp[i][j]%=MOD;
			}
		}
	} // dp部分
	int ans = 0;
	for (int j = 0;j<full;j++)
	{
		ans+=dp[(n-1)][j];
		ans%=MOD;
	}
	printf("%d", ans%MOD);
	return 0;
}

上面的代码是完全照着【1】打的. 但是很遗憾 MLE掉了. 但是和ac代码对拍过, 是没有问题的（速度也好,正确性也好, 都是合格的）.

怎么优化空间复杂度呢? 注意到上面dp[i][j] 的第一维i是可以滚动化的, 遂写下如下优化代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int MOD = 1e8;
int n,m, a[12][12],dp[2][1<<12], full; // 这里dp做了滚动处理

inline int ck(int i, int j)
{
	for (int k = 0; k<m; k++)
	{
		if (j>>k&1 && !a[i][k])
		{
			return 0;
		}
	}
	return 1;
}

int ck_int[1<<12];

inline int ck(int j)
{
	if (~ck_int[j])
	{
		return ck_int[j];
	}
	for (int i = 0,k = -100;i<m;i++)
	{
		if (j>>i&1)
		{
			if (i-k<=1)
			{
				return ck_int[j] = 0;
			}
			k =i;
		}
	}
	return ck_int[j] = 1;
}

inline int lowbit(int j)
{
	return j&-j;
}

int ckk_int_int[1<<12][1<<12];

inline int ckk(int k,int j)
{
	if (~ckk_int_int[k][j])
	{
		return ckk_int_int[k][j];
	}
	for (int i = 0;i<m;i++)
	{
		if ((k>>i&1) && (j>>i&1))
		{
			return ckk_int_int[k][j] = 0;
		}
	}
	return ckk_int_int[k][j] = 1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(ck_int, -1, sizeof(ck_int));
	memset(ckk_int_int, -1, sizeof(ckk_int_int));
	scanf("%d%d", &n,&m);
	for (int i = 0;i<n;i++)
	{
		for (int j = 0;j<m; j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	full = 1<<m;
	for (int j = 0;j<full; j++)
	{
		if (ck(0,j) && ck(j))
		{
			dp[0][j] = 1;
		}
	} 
	for (int i = 1;i<n; i++)
	{
		for (int j = 0;j<full;j++) // 第i行的状态是j
		{
			if (!ck(i,j) || !ck(j))
			{
				dp[i%2][j] = 0;
				continue;
			}
			for (int k = 0;k<full;k++) // 遍历所有合法的第i-1行的状态是k（其实我觉得比【1】的遍历顺序更符合人的思维，【1】中遍历是先遍历i-2行的状态的,现在想想有点没有这里自然）
			{
				if (!ck(i-1,k) || !ck(k) || !ckk(k,j))
				{
					continue;
				}
				dp[i%2][j]+=dp[(i-1)%2][k];
				dp[i%2][j]%=MOD;
			}
		}
		memset(dp[(i-1)%2], 0, sizeof(dp[(i-1)%2])); // 这是和【1】唯一不同之处, 因为这里是求和, 而不是求max. 每次循环是从(i-1)%2层推导i%2层, 所以每次用(i-1)%2层推导完i%2层之后, 要清空(i-1)%2层, 因为它是下一次的i%2层. 应该是0的
	} 
	int ans = 0;
	for (int j = 0;j<full;j++)
	{
		ans+=dp[(n-1)%2][j];
		ans%=MOD;
	}
	printf("%d", ans%MOD);
	return 0;
}

很遗憾, 还是MLE掉了. 原因也很显然, 因为上面的 ckk_int_int 太大了! 达到了 4096*4096*4/1024/1024 = 64MB之多! 而题目内存限制就是64MB， 所以MLE是显然的.

于是，我们将不再记忆化 ckk 的结果. 代价是速度变慢.

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int MOD = 1e8;
int n,m, a[12][12],dp[2][1<<12], full;

inline int ck(int i, int j)
{
	for (int k = 0; k<m; k++)
	{
		if (j>>k&1 && !a[i][k])
		{
			return 0;
		}
	}
	return 1;
}

int ck_int[1<<12];

inline int ck(int j)
{
	if (~ck_int[j])
	{
		return ck_int[j];
	}
	for (int i = 0,k = -100;i<m;i++)
	{
		if (j>>i&1)
		{
			if (i-k<=1)
			{
				return ck_int[j] = 0;
			}
			k =i;
		}
	}
	return ck_int[j] = 1;
}

inline int lowbit(int j)
{
	return j&-j;
}

inline int ckk(int k,int j)
{
	for (int i = 0;i<m;i++)
	{
		if ((k>>i&1) && (j>>i&1))
		{
			return 0;
		}
	}
	return 1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(ck_int, -1, sizeof(ck_int));
	scanf("%d%d", &n,&m);
	for (int i = 0;i<n;i++)
	{
		for (int j = 0;j<m; j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	full = 1<<m;
	for (int j = 0;j<full; j++)
	{
		if (ck(0,j) && ck(j))
		{
			dp[0][j] = 1;
		}
	} 
	for (int i = 1;i<n; i++)
	{
		for (int j = 0;j<full;j++)
		{
			if (!ck(i,j) || !ck(j))
			{
				dp[i%2][j] = 0;
				continue;
			}
			for (int k = 0;k<full;k++)
			{
				if (!ck(i-1,k) || !ck(k) || !ckk(k,j))
				{
					continue;
				}
				dp[i%2][j]+=dp[(i-1)%2][k];
				dp[i%2][j]%=MOD;
			}
		}
		memset(dp[(i-1)%2], 0, sizeof(dp[(i-1)%2])); 
	} 
	int ans = 0;
	for (int j = 0;j<full;j++)
	{
		ans+=dp[(n-1)%2][j];
		ans%=MOD;
	}
	printf("%d", ans%MOD);
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 144kB
Length 1494
Lang C++
Submitted 2019-11-02 20:00:11
Shared
RemoteRunId 21015538

参考

【1】https://yfsyfs.github.io/2019/10/31/poj-1185-%E7%82%AE%E5%85%B5%E9%98%B5%E5%9C%B0-%E7%BB%8F%E5%85%B8%E7%8A%B6%E5%8E%8BDP/