题目传送门
考虑到地形可以用二进制01表示，使用状压dp。
状压dp是采用十进制数字表示二进制的状态，实现状态的压缩。
如何设计状态，dp[层数][当前行的放置炮兵的情况][上一行放置炮兵的情况。
判断炮兵的放置情况要判断下面的情况是否合法：
- 左移右移一位两位相与的结果要为0
- 放置情况与地形相与的结果要为0
我们可以通过下面的代码来实现记录地形（grd数组）。
1
2
3
4
5
6
7
| for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char tmp;
cin>>tmp;
grd[i]=(grd[i]<<1)+(tmp=='H');
}
|
为了不误伤友军，我们需要通过二进制的左移和右移来判断是否会误伤。
我们用以下的代码，通过can数组来记录这个状态是否可用。
1
2
3
4
5
6
| for(int i=0;i<(1<<m);i++)
if(!(i&(i<<1))&&!(i&(i<<2))&&!(i&i>>1)&&!(i&i>>2))
{
can[i]=1;
if((i&grd[1])==0)dp[1][i][0]=res(i);
}
|
我们还可以顺便把dp的第一层给搞定。
res(i)是用来计算i在二进制下1的个数。
1
2
3
4
5
6
7
8
9
10
| int res(int i)
{
int cnt=0;
while(i)
{
if(i&1)cnt++;
i>>=1;
}
return cnt;
}
|
同理，我们通过枚举上一行和当前行的状态来进行dp。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
for(int A=0;A<(1<<m);A++)
if(can[A]&&(A&grd[1])==0)
for(int B=0;B<(1<<m);B++)
if(can[B]&&(B&grd[2])==0&&(A&B)==0)
dp[2][B][A]=dp[1][A][0]+res(B);
for(int i=3;i<=n;i++)
for(int A=0;A<(1<<m);A++)
if(can[A]&&(A&grd[i-2])==0)
for(int B=0;B<(1<<m);B++)
if(can[B]&&(B&grd[i-1])==0&&(A&B)==0)
for(int C=0;C<(1<<m);C++)
if(can[C]&&(C&grd[i])==0&&(C&A)==0&&(C&B)==0)
dp[i][C][B]=max(dp[i][C][B],dp[i-1][B][A]+res(C));
|
后面用ans统计答案。
1
2
3
4
| for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
for(int k=0;k<(1<<m);k++)
ans=max(ans,dp[i][j][k]);
|
相信大家的拼装能力肯定不错，能够把上面这些零件拼起来的。
完整答案：
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
| #include<bits/stdc++.h>
using namespace std;
int n,m,grd[110],dp[110][(1<<10)][(1<<10)];
bool can[(1<<10)];
int res(int i)
{
int cnt=0;
while(i)
{
if(i&1)cnt++;
i>>=1;
}
return cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char tmp;
cin>>tmp;
grd[i]=(grd[i]<<1)+(tmp=='H');
}
for(int i=0;i<(1<<m);i++)
if(!(i&(i<<1))&&!(i&(i<<2))&&!(i&i>>1)&&!(i&i>>2))
{
can[i]=1;
if((i&grd[1])==0)dp[1][i][0]=res(i);
}
for(int A=0;A<(1<<m);A++)
if(can[A]&&(A&grd[1])==0)
for(int B=0;B<(1<<m);B++)
if(can[B]&&(B&grd[2])==0&&(A&B)==0)
dp[2][B][A]=dp[1][A][0]+res(B);
for(int i=3;i<=n;i++)
for(int A=0;A<(1<<m);A++)
if(can[A]&&(A&grd[i-2])==0)
for(int B=0;B<(1<<m);B++)
if(can[B]&&(B&grd[i-1])==0&&(A&B)==0)
for(int C=0;C<(1<<m);C++)
if(can[C]&&(C&grd[i])==0&&(C&A)==0&&(C&B)==0)
dp[i][C][B]=max(dp[i][C][B],dp[i-1][B][A]+res(C));
int ans=0;
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
for(int k=0;k<(1<<m);k++)
ans=max(ans,dp[i][j][k]);
cout<<ans;
return 0;
}
|