poj 1185 炮兵阵地 经典状压DP

缘起

经典状压DP~ poj 1185 炮兵阵地

分析

1
2
3
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山
地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上
不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
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
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右
各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支
炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。
N <= 100；M <= 10。

Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output
6

限制
2s

来源
01 NOI

此题目是经典的状压DP。 状压DP体现在后面的状态仅仅依赖前面的状态. 本题因为M较小（<=10）, 所以一行炮兵的摆法完全可以使用状态压缩. 而且一行的摆法仅仅和它上2行的摆法有关。令

1
2
3
4
5
6
dp[i][j][k] 是第i行的状态是k, 第i-1行是j时最多能摆下的炮兵数量.则
dp[i][j][k] = max_{for t}{dp[i][j][k], dp[i-1][t][j]+num(k)}, N>i>=2
因为涉及到上上行摆法,所以需要初始化dp[0][i][j]和dp[1][i][j], 其中 dp[0][i][j] 表示第0行的状态是j时,最多放几个炮兵. dp[1][i][j] 表示第1行的状态是j, 第0行的状态是i时最多放几个炮兵
答案显然就是 dp[N-1][i][j]中的最大值(for i for j). 
注意, 因为涉及位运算, 所以最好所有的索引都从0开始而不是从1开始
而且显然可以使用无脑滚动数组优化空间复杂度，不然容易MLE

则写下下面的代码

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
//#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 100, maxm = 10;
int n,m, dp[2][1024][1024],full;
bool mp[maxn][maxm]; // true表示可以放置炮兵, 否则不可以

bool ck(int i, int j) // 第i行是否允许状态为j
{
	for (int x = 0,y = -100;x<m;x++) // y记录前一个x
	{
		if (j&(1<<x)) // 如果炮兵放在第x列
		{
			if (!mp[i][x])// 炮兵不能放置在山坡上
			{
				return false;
			}
			if (x-y<=2) // 和上一次的x距离<=2, 则不行
			{
				return false;
			}
			y = x; // 更新y
		}
	} 
	return true;
}

bool ck(int i, int j, int k) // 第i行是否允许状态为j, 其中第i-1行(即上一行)的状态是k
{
	if (!ck(i,j))
	{
		return false;
	}
	for (int x = 0;x<m;x++)
	{
		if (j&(1<<x)) 
		{
			if (k&(1<<x)) // 如果会攻击到上一行的炮兵, 则不行
			{
				return false;
			}
		}
	} 
}

bool ck(int i, int j, int k, int l) // 第i行是否允许状态是j, 其中i-1行状态是k, 第i-2行的状态是l
{
	if (!ck(i,j,k))
	{
		return false;
	}
	for (int x = 0;x<m;x++)
	{
		if (j&(1<<x)) 
		{
			if (l&(1<<x)) // 如果会攻击到上上行的炮兵, 则不行
			{
				return false;
			}
		}
	} 
	return true;
}


int lowbit(int i)
{
	return i&-i;
}

int tot(int i) // 状态i包含的1的个数
{
	int ans = 0;
	while(i)
	{
		++ans;
		i-=lowbit(i);
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n ,&m);
	full = 1<<m; // 0,...,full-1是每行状态的总数
	for (int i = 0;i<n;i++)
	{
		getchar();
		for (int j = 0;j<m;j++)
		{
			char c = getchar();
			if (c=='P')
			{
				mp[i][j] = true;
			}
		}
	}
	for (int j = 0;j<full; j++) // 第0行的状态
	{
		if (!ck(0,j)) // 如果第0行不允许是j
		{
			continue;
		}
		for (int i = 0;i<full;i++) // 第-1行是随意的
		{
			dp[0][i][j] = tot(j); // 第0行的dp值其实和i无关
		}
	} // 初始化 dp[0][i][j], j是第0行状态, i是第-1行状态(随意)
	for (int i = 0;i<full; i++) // 第0行的状态是i
	{
		if (!ck(0,i)) // 如果第0行不允许是i
		{
			continue;
		}
		for (int j = 0;j<full;j++) // 第一行的状态是j
		{
			if (!ck(1,j,i)) // 如果第1行不允许是j
			{
				continue;
			}
			dp[1][i][j] = max(dp[1][i][j], dp[0][j][i]+tot(j));
		}
	} // 初始化 dp[1][i][j], j是第1行状态, i是第0行状态
	for (int i = 2;i<n;i++) // 第i行
	{
		for (int t = 0;t<full; t++) // 第i-2行的状态是t
		{
			if (!ck(i-2,t))
			{
				continue;
			}
			for (int j = 0;j<full;j++) // 第i-1行的状态是j
			{
				if (!ck(i-1,j,t))
				{
					continue;
				}
				for (int k = 0;k<full; k++) // 第i行的状态是k
				{
					if (!ck(i,k,j,t))
					{
						continue;
					}
					dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][t][j]+tot(k));
				}
			}
		}
	} // 开始dp
	int ans = 0;
	for (int i = 0;i<full;i++)
	{
		for (int j = 0; j<full; j++)
		{
			ans = max(ans, dp[(n-1)%2][i][j]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

在洛谷上全部wa, 这个和在【1】中说过了, 应该是洛谷对于字符getchar的处理的问题. 在poj上死活wa, 但是已经和ac程序对拍无数次. 都没有问题. 不造为啥? 感觉poj可能是哪里发神经了. 然后跑到 vijos（ 炮兵阵地）上去提交.

结果在10个点中最后那个点被T掉了. 所以一定是哪里慢了.

其实稍微注意一下就知道哪里慢了——反复调用ck函数, 而ck函数其实是两部分杂糅在一起了. 第一部分是和行号有关的——确切讲就是和mp有关. 第二部分是和行号无关的. 即本行的状态和上一行的状态. 这部分其实完全可以记忆化的. 即和行号无关的部分是可以记忆化提高速度的. 所以我们应该把 ck 中的和行号无关的 、和行号有关的两部分拆出来. 然后对和行号无关的部分进行记忆化.

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
//#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 100, maxm = 10;
int n,m, dp[2][1024][1024],full;
bool mp[maxn][maxm]; // true表示可以放置炮兵, 否则不可以
int ckk_int[1024]; // 记忆化ckk(int)的结果

inline bool ckk(int j) // 注意, 一定要加inline, 可以缩减2/3的时间, 很惊人！
{
	if (~ckk_int[j])
	{
		return ckk_int[j];
	}
	for (int x = 0,y = -100;x<m;x++) // y记录前一个x
	{
		if (j&(1<<x)) // 如果炮兵放在第x列
		{
			if (x-y<=2) // 和上一次的x距离<=2, 则不行
			{
				return ckk_int[j] = 0;
			}
			y = x; // 更新y
		}
	} 
	return ckk_int[j] = 1;
}

inline bool ck(int i, int j) // 第i行是否允许状态为j
{
	if (!ckk(j))
	{
		return false;
	}
	for (int x = 0;x<m;x++)
	{
		if (j&(1<<x))
		{
			if (!mp[i][x])// 炮兵不能放置在山坡上
			{
				return false;
			}
		}
	} 
	return true;
}

int ckk_int_int[1024][1024];  // 记忆化ckk(int,int)的结果, 即本行的某个状态和上一行的某个状态是否可行

inline bool ckk(int j, int k)
{
	if (~ckk_int_int[j][k])
	{
		return ckk_int_int[j][k];
	}
	for (int x = 0;x<m;x++)
	{
		if (j&(1<<x)) 
		{
			if (k&(1<<x)) // 如果会攻击到上一行的炮兵, 则不行
			{
				return ckk_int_int[j][k] = 0;
			}
		}
	} 
	return ckk_int_int[j][k] = 1;
}

inline bool ck(int i, int j, int k) // 第i行是否允许状态为j, 其中第i-1行(即上一行)的状态是k
{
	return ck(i,j) && ckk(j,k);
}

int cckk_int_int[1024][1024]; // 记忆化cckk(int,int)的结果, 即本行的某个状态和上上行的某个状态是否可行

inline bool cckk(int j, int k)
{
	if (~cckk_int_int[j][k])
	{
		return cckk_int_int[j][k];
	}
	for (int x = 0;x<m;x++)
	{
		if (j&(1<<x)) 
		{
			if (k&(1<<x)) // 如果会攻击到上上一行的炮兵, 则不行
			{
				return cckk_int_int[j][k] = 0;
			}
		}
	} 
	return cckk_int_int[j][k] = 1;
}

inline bool ck(int i, int j, int k, int l) // 第i行是否允许状态是j, 其中i-1行状态是k, 第i-2行的状态是l
{
	return ck(i,j,k) && cckk(j,l);
}


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

inline int tot(int i) // 状态i包含的1的个数
{
	int ans = 0;
	while(i)
	{
		++ans;
		i-=lowbit(i);
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(ckk_int, -1, sizeof(ckk_int));
	memset(ckk_int_int, -1, sizeof(ckk_int_int));
	memset(cckk_int_int, -1, sizeof(cckk_int_int));
	scanf("%d%d", &n ,&m);
	full = 1<<m; // 0,...,full-1是每行状态的总数
	for (int i = 0;i<n;i++)
	{
		getchar();
		for (int j = 0;j<m;j++)
		{
			char c = getchar();
			if (c=='P')
			{
				mp[i][j] = true;
			}
		}
	}
	for (int j = 0;j<full; j++) // 第0行的状态
	{
		if (!ck(0,j)) // 如果第0行不允许是j
		{
			continue;
		}
		for (int i = 0;i<full;i++) // 第-1行是随意的
		{
			dp[0][i][j] = tot(j); // 第0行的dp值其实和i无关
		}
	} // 初始化 dp[0][i][j], j是第0行状态, i是第-1行状态(随意)
	for (int i = 0;i<full; i++) // 第0行的状态是i
	{
		if (!ck(0,i)) // 如果第0行不允许是i
		{
			continue;
		}
		for (int j = 0;j<full;j++) // 第一行的状态是j
		{
			if (!ck(1,j,i)) // 如果第1行不允许是j
			{
				continue;
			}
			dp[1][i][j] = max(dp[1][i][j], dp[0][j][i]+tot(j));
		}
	} // 初始化 dp[1][i][j], j是第1行状态, i是第0行状态
	for (int i = 2;i<n;i++) // 第i行
	{
		for (int t = 0;t<full; t++) // 第i-2行的状态是t
		{
			if (!ck(i-2,t))
			{
				continue;
			}
			for (int j = 0;j<full;j++) // 第i-1行的状态是j
			{
				if (!ck(i-1,j,t))
				{
					continue;
				}
				for (int k = 0;k<full; k++) // 第i行的状态是k
				{
					if (!ck(i,k,j,t))
					{
						continue;
					}
					dp[i%2][j][k] = max(dp[i%2][j][k], dp[(i-1)%2][t][j]+tot(k));
				}
			}
		}
	} // 开始dp
	int ans = 0;
	for (int i = 0;i<full;i++)
	{
		for (int j = 0; j<full; j++)
		{
			ans = max(ans, dp[(n-1)%2][i][j]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Accepted

# 状态 耗时 内存占用
#1 Accepted 6ms 11.602 MiB
#2 Accepted 5ms 11.59 MiB
#3 Accepted 128ms 16.234 MiB
#4 Accepted 49ms 16.047 MiB
#5 Accepted 170ms 14.387 MiB
#6 Accepted 268ms 15.914 MiB
#7 Accepted 260ms 15.934 MiB
#8 Accepted 48ms 16.191 MiB
#9 Accepted 14ms 14.566 MiB
#10 Accepted 536ms 14.816 MiB

参考

【1】https://yfsyfs.github.io/2019/09/22/%E6%B4%9B%E8%B0%B7-P1019-%E5%8D%95%E8%AF%8D%E6%8E%A5%E9%BE%99/