「NOI2001」炮兵阵地

发表于 | 分类于 ，

哎呀！图片走丢了！

题目描述

司令部的将军们打算在$N\ast M$的网格地图上部署他们的炮兵部队。一个$N\ast M$的地图由$N$行$M$列组成，地图的每一格可能是山地（用”H” 表示），也可能是平原（用”P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
哎呀！图片走丢了！

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入格式

第一行包含两个由空格分割开的正整数，分别表示$N$和$M$；

接下来的$N$行，每一行含有连续的$M$个字符（’P’或者’H’），中间没有空格。按顺序表示地图中每一行的数据。$N\leq100$；$M\leq10$。

输出格式

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

样例输入
1
2
3
4
5
6
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
样例输出
1
6
思路

这是一道状压DP的毒瘤基础题，因为每个炮兵会影响它下面两行，所以状压时要压两行。枚举每一行的时候只需要判断它上面两行是否有炮兵和该处是否是山丘

如果我们用$f[i][j][k]$表示，第$k$行的状态为$j$，第$k-1$行的状态为$i$时的炮兵数，那么状态转移方程可以轻松推出：

这里的$q$为第$k-2$行的状态，$sum[j]$为状态$j$中有几个$1$。

状态转移方程出来了，剩下的就是细节了。

一、如何判断同一行的炮兵是否相互攻击

由于每个炮兵可以攻击向左或向右两格。所以我们可以把状态$S$左位移两位，然后与$S$做与运算，如果结果为$1$说明有一些炮兵会相互攻击，为$0$则没有，大家模拟一下就能明白其中的原理。同时，我们还需要再做一下左位移一位后的与运算，这样就能判断两格内是否有其他炮兵了。体现到代码上就是(S<<2)&S和(S<<1)&S

二、如何判断某处是否是山地

这就很简单了，只需要对读入的图也进行状压，将每一行变成一个二进制数（山地为$1$，平原为$0$），然后将状态与对应的那一行做与运算，结果为$0$，说明不冲突，为$1$则冲突。

三、如何判断某一列上是否有炮兵相互攻击

这只需要将这一行与上两行的状态做与运算，为$1$则冲突，为$0$则不冲突。

四、好像会爆内存啊，怎么办啊？

因为每一行只与上两行有关，所以我们可以使用滚动数组来降低内存。

另：（划重点！！！）

在写状压DP时，位运算一定要加括号，因为一些运算的优先级是高于位运算的，

所以一定要加括号！！！。别问我是咋知道的

代码
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
#include<iostream>
#include  <cstdio>
#define I_love_Yae_Sakura int main()
#define ri register int
using namespace std;
const int maxn=110,maxm=4096;
int ans,state,map[maxn],sum[maxm],f[maxm][maxm][3];
inline int get(int x)
{
    int num=0;
    while(x)
    {
        if(x&1)
            num++;
        x>>=1;
    }
    return num;
}
I_love_Yae_Sakura
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(ri i=1;i<=n;i++)
        for(ri j=1;j<=m;j++)
        {
            char ch;
            cin>>ch;
            map[i]<<=1;
            if(ch=='H')
                map[i]+=1;
        }
    state=(1<<m)-1;
    for(ri i=0;i<=state;i++)
        sum[i]=get(i);
    for(ri i=0;i<=state;i++)
        for(ri j=0;j<=state;j++)
            if(!(i&j) && !((i<<2)&i) && !((i<<1)&i) && !((j<<2)&j) && !((j<<1)&j) && !(map[1]&i) && !(map[2]&j))
                f[i][j][1]=sum[i]+sum[j];
    for(ri i=3;i<=n;i++)
        for(ri j=0;j<=state;j++)
            if(!(map[i-1]&j) && !((j<<2)&j) && !((j<<1)&j))
                for(ri k=0;k<=state;k++)
                    if(!(map[i]&k) && !((k<<2)&k) && !((k<<1)&k) && !(j&k))
                        for(ri q=0;q<=state;q++)
                            if(!(map[i-2]&q) && !((q<<2)&q) && !((q<<1)&q) && !(q&j) && !(q&k))
                                f[j][k][(i-1)%3]=max(f[j][k][(i-1)%3],f[q][j][(i-2)%3]+sum[k]);
    for(ri i=0;i<=state;i++)
        for(ri j=0;j<=state;j++)
            ans=max(ans,f[i][j][(n-1)%3]);
    cout<<ans<<endl;
    return 0;
}
0%