炮兵阵地[蕾姆我老婆]

· · 题解

题目描述

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

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

输入输出格式

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

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

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

输入输出样例

输入样例#1:

5 4

PHPP

PPHH

PPPP

PHPP

PHHP 输出样例#1：

6 首先看到这道题的数据范围M≤10,状态的数据范围只有十位很容易就想到了状压dp。题目的输入是字母要先装换成数字，用‘1’表示‘P’，用‘0’表示‘H’。同时把每一排的状态合在一起组成一个数。然后先预处理，把每一排有可能的状态先存下来（这时候先不考虑原本的图，等之后用到的时候再判断）。一般的状压dp要先预处理的一排，但这道题他的攻击范围有两排，所以要预处理两排。因此要开一个三位数组 s2[n][1<<m][1<<m],存现在在第几排，上一排的状态和现在的状态，存在这个状态的方案数，然后在判断是否与上一排和上上一排重合判断是否合法（攻击得到）。最后枚举一下最后一排的方案取最大值就好了。 代码如下：

include<bits/stdc++.h>

using namespace std;

int s1[110];

int s2[11];

int s3[1<<10],s4[1<<10];

int sss[110][1<<10][1<<10];

int n,m,shu=0;

int fa(int i)

{

      int ss=0;

      while(i!=0)

      {

            if(i&1)

            ss++;

            i=i>>1;

      }

      return ss;

}

bool pan(int i)

{

      int s=i<<1;

      int ss=i>>1;

      int a=i<<2;

      int aa=i>>2;

      if((i&s)||(i&ss)||(i&a)||(i&aa))

            return false;

      else

            return true;

}

bool pan(int a,int b)

{

      if(a&b)

            return false;

      b=b<<1;

      if(a&b)

        return false;

      b=b<<1;

      if(a&b)

        return false;

      return true;

}

int main()

{

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char ss[12];
        scanf("%s",ss);
        for(int j=0;j<m;j++)
          {
             if(ss[j]=='P')
                 s1[i]=s1[i]+1;
             s1[i]=s1[i]<<1;
          }

     s1[i]=s1[i]>>1;
    }
    s2[0]=1;
    for(int i=1;i<=m;i++)
        s2[i]=s2[i-1]<<1;
    for(int i=0;i<s2[m];i++)
    {
            if(pan(i))
            {
                shu++;
                s3[shu]=i;
                s4[shu]=fa(i);
            }
    }
    for(int i=1;i<=shu;i++)//1
    {
        if((s3[i]&s1[1])==s3[i])
          {
                sss[1][0][s3[i]]=s4[i];
                for(int j=1;j<=shu;j++)//2
                {
                  if((s3[j]&s1[2])==s3[j]&&!(s3[i]&s3[j]))
                    {
                      sss[2][s3[i]][s3[j]]=max(sss[2][s3[i]][s3[j]],sss[1][0][s3[i]]+s4[j]);
                     }
                }
          }
    }

    for(int i=3;i<=n;i++)

    {

            for(int j=1;j<=shu;j++)//1

            {

                    if((s3[j]&s1[i-2])==s3[j])

                    {

                          for(int k=1;k<=shu;k++)//2

                                  {

                                  if((s3[k]&s1[i-1])==s3[k]&&!(s3[j]&s3[k]))

                                          {

                                          for(int h=1;h<=shu;h++)//3
                                                  {

                                                  if((s3[h]&s1[i])==s3[h]&&!(s3[h]&s3[k])&&!(s3[h]&s3[j]))

                                                  {

                                                  sss[i][s3[k]][s3[h]]=max(sss[i][s3[k]]s3[h]],sss[i-1][s3[j]][s3[k]]+s4[h]);

                                                 }
                                          }
                                  }
                          }
                    }
            }
    }
    int ans=0;
    for(int i=1;i<=shu;i++)
    {
          for(int j=1;j<=shu;j++)
          ans=max(ans,sss[n][s3[j]][s3[i]]);
    }
    printf("%d",ans);
    return 0;

}