这题其实是动规+状态压缩。
最基本的压缩想法是：二进制压缩，若第i个地方放了大炮，那么该位就为1。
题目中的列数m很少，m<=10，可以在不考虑地形的情况下计算出一行的所有可能情况，也就是一行的标准情况。那么其余行的状态必定为这些标准状态之一。这些标准状态可以用O(2^m)的时间枚举出来，经实践证明，当m=10时标准状态只有60种，这样一来，每行的状态数不超过60种。
另外一方面，因为一个炮兵会影响到它下面的两行，因此我们在转移的时候需要记下当前行和上一行的状态。用f[i,j,k]表示第i行的状态为标准状态j，第i-1行的状态为标准状态k，那么f[i,j,k]=max{f[i-1,k,u]}+o[j] （其中o[j]表示标准状态j中有多少个炮兵）
最后的答案就是max{f[n,j,k]}
因为这题用到了许多的位运算小技巧，所以在这里顺便提下（其实这些小技巧可以直接看程序）：
-
要验证某一行的状态i是否可行，也就是验证是否有两个连续的二进制位1：((i<<1)&i==0) && ((i<<2)&i==0)
-
要验证某一行是否会和上一行冲突，也就是验证两行有没有同为1的二进制位：!(s[i]&s[j])
-
枚举标准状态，只需要一个0~2m-1的for循环。
-
要统计出某个数x它的二进制位中有多少个1，可以使用一种基于二分思想的O(1)算法，见程序中的int CountOne(int)。详细的解释可以参考位运算简介及实用技巧（二）：进阶篇(1) @ Matrix67大牛。
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
| #include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,States,s[60],o[60],f[101][60][60],map[101];
inline int CountOne(int x) {
x=(x&0x55555555) + ((x>>1) &0x55555555);
x=(x&0x33333333) + ((x>>2) &0x33333333);
x=(x&0x0f0f0f0f) + ((x>>4) &0x0f0f0f0f);
x=(x&0x00ff00ff) + ((x>>8) &0x00ff00ff);
x=(x&0x0000ffff) + ((x>>16)&0x0000ffff);
return x;
}
void GetStates() {
for (int i=0;i<=(1<<m)-1;++i)
if ((i&i<<1)==0 && (i&i<<2)==0) {
s[States]=i;
o[States++]=CountOne(i);
}
}
int main() {
memset(f,193,sizeof(f));
ios::sync_with_stdio(false);
cin>>n>>m;
GetStates();
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) {
char x;
cin>>x;
map[i]<<=1;
if (x=='H') map[i]|=1;
}
for (int j=0;j<States;++j) if (!(s[j]&map[1])) f[1][j][0]=o[j];
for (int i=2;i<=n;++i)
for (int j=0;j<States;++j) if (!(s[j]&map[i]))
for (int k=0;k<States;++k) if (!(s[k]&map[i-1]) && !(s[j]&s[k])) {
for (int u=0;u<States;++u) if (!(s[u]&map[i-2]) && !(s[u]&s[k]) && !(s[u]&s[j]))
f[i][j][k]=max(f[i][j][k],f[i-1][k][u]);
f[i][j][k]+=o[j];
}
int ans=0;
for (int j=0;j<States;++j)
for (int k=0;k<States;++k)
ans=max(ans,f[n][j][k]);
cout<<ans;
}
|
