POJ 1185 炮兵阵地（状压DP）

时间：2021-12-16 23:35:07
炮兵阵地
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 26426   Accepted: 10185

Description

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

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

Input

第一行包含两个由空格分割开的正整数，分别表示N和M； 
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

Output

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

Sample Input

5 4

PHPP

PPHH

PPPP

PHPP

PHHP

Sample Output

6

题目链接：POJ 1185

以前一直想做来着，写了ZOJ上的Firenet以为这是个差不多的二分匹配，可惜连样例都过不了（这就非常尴尬了）后来发现不一定是二分图，后来发现是普通图求最大独立集，照着别人的最大独立集模版写了一个过了，然而现在也不会最大独立集…………

改了一个下午的状压DP，结果连样例都过不了，因为里面的细节错误实在是太多，晚上删了重新写就1A了……

用$dp[i][j][k]$表示当前第$i$行，第$j$种状态（为什么是种而不是直接的二进制转换十进制$j$后面会讲）且前一行的状态为$k$。

显然由状压基本法可以推出：$dp[i][j][k]=max(dp[i][j][k],dp[i-1][第i-1行的第j'个状态][第i-2行的第k'个状态]+cnt[j]$。

但是由于$m<=10$，如果用普通的二进制再转十进制，DP数组则变成了$N*(1<<M)*(1<<M)$有1E多了，直接MLE，然后学习一下大牛的做法，先把所有可能的状态预处理出来，然后用i代表示在预处理的状态中第$i$个状态，这样一来状态就只有最多60种了（假设M=10且全部都是平原，则状态总数刚好就是60），再用$cnt[i]$表示第i种状态摆了几个，还是偷懒用$bitset::count$就行了，对于平原和山地的处理，把平原看成1把山地看成0虽然便于理解，但是判断起来不方便，因此要反过来把山地H看成1，若山地为1一旦有一个炮兵位置为1，则结果肯定不为0，这样判断是否安放了炮兵在山地上就很简单了，然后就是按照以前的思路，多一个for处理第$i-2$行的状态即可，一些坑点注释在代码里了

代码：

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=105;

const int M=12;

const int S=65;

char pos[N][M];

int dp[N][S][S];

int row_bid[N];

int sta[S],cnt[S],tot,n,m;

inline bool check(const int &a,const int &b)

{

    return (a&b)==0;

}

void init()

{

    CLR(dp,0);

    int R=1<<m;

    tot=0;

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

    {

        if(check(i,i<<1)&&check(i,i<<2))

        {

            sta[tot]=i;

            cnt[tot]=(int)bitset<11>(i).count();

            ++tot;

        }

    }

}

int main(void)

{

    int i,j,k,p;

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

    {

        init();//数组初始化以及预处理出本身就合法的状态

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

        {

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

            int temp=0;

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

            {

                temp<<=1;

                temp=temp+(pos[i][j]=='H');//这里加个括号，否则先算+号再算==号就出问题了

            }

            row_bid[i]=temp;

        }

        //第一行初始化

        for (i=0; i<tot; ++i)

        {

            if(check(sta[i],row_bid[0]))

                dp[0][i][0]=cnt[i];

        }

        //第二行初始化

        for (i=0; i<tot; ++i)//当前行(1)

        {

            if(check(sta[i],row_bid[1]))

            {

                for (j=0; j<tot; ++j)//上一行(0)

                {

                    if(check(sta[j],row_bid[0])&&check(sta[i],sta[j]))

                    {

                        dp[1][i][j]=max<int>(dp[1][i][j],dp[0][j][0]+cnt[i]);

                    }

                }

            }

        }

        //后面进行DP

        for (i=2; i<n; ++i)//每一行

        {

            for (j=0; j<tot; ++j)//当前行

            {

                if(check(row_bid[i],sta[j]))

                {

                    for (k=0; k<tot; ++k)//上一行

                    {

                        if(check(row_bid[i-1],sta[k])&&check(sta[j],sta[k]))

                        {

                            for (p=0; p<tot; ++p)//上上行

                            {

                                if(check(row_bid[i-2],sta[p])&&check(sta[k],sta[p])&&check(sta[j],sta[p]))

                                {

                                    dp[i][j][k]=max<int>(dp[i][j][k],dp[i-1][k][p]+cnt[j]);

                                }

                            }

                        }

                    }

                }

            }

        }

        int maxm=0;

        for (i=0; i<tot; ++i)

            for (j=0; j<tot; ++j)

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

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

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

    }

    return 0;

}

相关文章