POJ：1185-炮兵阵地（状压dp入门）

2021-10-13 23:06:17

炮兵阵地

Time Limit: 2000MS Memory Limit: 65536K

Description

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

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

Input

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

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

Output

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

Sample Input

5 4

PHPP

PPHH

PPPP

PHPP

PHHP

Sample Output

解题心得：

状压dp，很神奇啊，一般状压dp的标志就是某一数据量比较小，例如，行的长度很大，列的长度在15以下，可以直接使用二进制01表示状态，然后化为十进制，用一个数来表示每一行的状态。
这个题其实也可以说是二进制枚举，用一个二进制数来表示一行的状态，筛出一些不符合要求的数，例如，同一行中两个炮台在一行之中距离小于3，这样就可以筛去一大部分数（1000个数可以筛去930个左右）。然后枚举每一行的可以安排炮塔的状态，枚举的时候检验是否和前面已经安排的炮塔产生冲突，如果不产生冲突，那么记录下不产生冲突的情况下可以安排的最多的炮塔的数量。
状态转移是在从前面安排好的炮塔的状态来转移出下面可以安排的炮塔，并且既要符合前面安排好的炮塔，还要得到可以安排炮塔的最大值。dp[i][j][k]代表的是前面i行最多可以安排k个炮塔，前i-1行可以安排j个炮塔。转移方程式为：
- dp[i][j2][j1] = max(dp[i][j2][j1],dp[i-1][j3][j2]+sum[j1])
有点复杂，不懂得可以看看实现的方法。

#include<stdio.h>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 110;

int maps[maxn],sum[maxn],stk[maxn],cnt,dp[maxn][maxn][maxn];

char s[maxn][maxn];

int n,m;

void init()

{

    cnt = 0;

    memset(dp,-1,sizeof(dp));

    memset(maps,0,sizeof(maps));

    memset(sum,0,sizeof(sum));

    memset(stk,0,sizeof(stk));

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

    {

        scanf("%s",s[i]);

        for(int j=0;j<m;j++)

            if(s[i][j] == 'H')

                maps[i] |= (1<<(m-j-1));//用一个数来表示地图上山峰的情况

    }

}

bool ok(int x)//这个数是否符合一行中安排炮塔的条件（每个炮塔距离大于2）

{

    if(x&(x<<1))

        return false;

    if(x&(x<<2))

        return false;

    return true;

}

int get_sum(int x)//记录这个数代表的状态中有多少个炮塔

{

    int sum = 0;

    while(x)

    {

        if(x & 1)

            sum++;

        x>>=1;

    }

    return sum;

}

void get_stk()

{

    for(int i=0;i<(1<<m);i++)

        if(ok(i))//检验这个数是否符合一行中安排炮塔的条件（每个炮塔的距离大于2）

        {

            stk[cnt] = i;

            sum[cnt++] = get_sum(i);//记录这个状态中有多少个炮塔

        }

}

int get_ans()

{

    for(int i=0;i<cnt;i++)

        if(!(maps[0] & stk[i]))//第一行比价特殊只要不和地图冲突就可以了

            dp[0][0][i] = sum[i];

    for(int i=1;i<n;i++)//安排每一行

        for(int j1=0;j1<cnt;j1++)//枚举每一行安排炮塔的情况

        {

            if(maps[i]&stk[j1])//枚举的当前状态是否和地图上的山峰冲突

                continue;

            for(int j2=0;j2<cnt;j2++)//枚举的当前状态是否和上一行冲突

            {

                if(stk[j2] & stk[j1])

                    continue;

                for(int j3=0;j3<cnt;j3++)//枚举的当前状态是否和上上行冲突

                {

                    if(stk[j3] & stk[j1])

                        continue;

                    dp[i][j2][j1] = max(dp[i][j2][j1],dp[i-1][j3][j2]+sum[j1]);//找出不冲突的最大炮塔数量

                }

            }

        }

    int Max = 0;

    for(int i=0;i<cnt;i++)

        for(int j=0;j<cnt;j++)

            if(dp[n-1][i][j] > Max)

                Max = dp[n-1][i][j];

    return Max;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();//初始化各值

        get_stk();

        int ans = get_ans();

        printf("%d\n",ans);

    }

    return 0;

}

码农公寓