P2704 [NOI2001]炮兵阵地

题目描述

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例#1：

Solution：

　　本题状压dp水题。

　　定义$f[i][j][k]$表示前$i$行最后两行状态为$j,k$的最大放置数（第一维显然可以滚掉）。

　　先预处理出单行的合法状态和放置部队数，然后转移时就二进制捣鼓一下判断合法（注意特判第一行的情况），最后枚举后两行的状态，求最大值就好了。

代码：

/*Code by 520 -- 10.17*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int M=11;
int n,m,cnt,f[2][1<<M][1<<M],mp[105],w[1<<M];
bool sta[1<<M];

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m; char c; int lim=(1<<m)-1;
    For(i,0,lim) {
        if((i<<1)&i||(i<<2)&i) continue;
        if((i>>1)&i||(i>>2)&i) continue;
        For(j,0,m-1) if(i&(1<<j)) w[i]++;
        sta[i]=1;
    }
    For(i,1,n) For(j,1,m) cin>>c,mp[i]+=(c=='P'?(1<<j-1):0);
    For(i,1,n) {
        For(j,0,lim) if(sta[j]&&((j&mp[i-1])==j)){
            For(k,0,lim)
                if(sta[k]&&(i==1||(k&mp[i-2])==k)&&(!(j&k)))
                For(p,0,lim) if(sta[p]&&(!(p&k))&&(!(p&j))&&(p&mp[i])==p)
                    f[cnt^1][j][p]=max(f[cnt^1][j][p],f[cnt][k][j]+w[p]);
            }
        cnt^=1;
    }
    int ans=0;
    For(i,0,lim) if(sta[i]&&(i&mp[n-1])==i)
    For(j,0,lim) if(sta[j]&&(j&mp[n])==j&&!(i&j)) ans=max(ans,f[cnt][i][j]);
    cout<<ans;
    return 0;
}