POJ-1185: 炮兵阵地

状压DP

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

6

分析：每个格子对应的状态有两种，放炮兵和不放炮兵，因此这道题我们可以用状态压缩DP来做。由于m为列数，是小于等于10的，因此初步看起来，有$2^{10}种状态，但是其实并不是这样的，因为题目有限制，保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内，那么状态就缩小到了不到70种。我们可以预先处理出可行的状态，并且统计出每种有效状态中1的个数（即放置炮兵的个数）。

接下来就是dp的环节了。对于数组dp[i][j][k]，我们表示第i行的状态为st[j]，第i-1行的状态为st[k]时候的最优解（st数组表示有效的放置）。
那么第i行的状态可以由上一行的状态推出，则有状态转移方程：

$$dp[i][j][k]=max\{dp[i-1][k][kk]+num[j]\}$$

• 代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char mp[111][11];//从mp[1]开始
int st[70],cnt; //有效状态，个数
int num[70];//每个有效状态中1的个数
int now[111];//现在每一行的状态用二进制表示，从1开始
int dp[111][70][70];//第i行状态为st[j]，i-1行状态为st[k]的最优解
int n,m;
int one(int i) //统计1的个数
{
    int n=0;
    while(i)
    {
        if(i%2==1)
            n++;
        i/=2;
    }
    return n;
}
void valid() //有效状态
{
    int mask=(1<<m);
    for(int i=0;i<mask;i++)
    {
        if((!(i&(i<<1)))&&(!(i&(i<<2)))) //i的左右各两个都为0，合法
        {
            st[cnt]=i;
            num[cnt++]=one(i);
        }
    }
}
int main()
{
    int i,j,k,kk,ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(now,0,sizeof(now));
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        memset(st,0,sizeof(st));
        ans=0,cnt=0;
        valid();
        for(i=1;i<=n;i++) //从第二行开始，第一行空出来，now[0]就全为0，当作全是空地
        {
            scanf("%s",mp[i]);
            for(j=0;j<m;j++)
                if(mp[i][j]=='H')
                now[i]+=(1<<(m-j-1)); //处理输入的地图为n行二进制数
        }
       /* for(i=1;i<=n;i++)
            printf("%d\n",now[i]);*/
        for(i=0;i<cnt;i++)
        {
            if(!(now[1]&st[i]))//不冲突
            {
                dp[1][i][0]=num[i];
                ans=max(ans,num[i]);
              //  printf("%d %d\n",ans,st[i]);
            }
        }
        for(i=2;i<=n;i++)
        {
            for(j=0;j<cnt;j++)//这一行
            {
                if(!(now[i]&st[j]))//这行和可行状态不冲突，填充
                for(k=0;k<cnt;k++)
                {
                    if(!(st[j]&st[k]))//上行和这行不冲突
                    for(kk=0;kk<cnt;kk++)
                    if((!(st[kk]&st[k]))&&(!(st[kk]&st[j])))//上行和上上行不冲突,这行也和上上行不冲突
                        dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][kk]+num[j]);
                    ans=max(ans,dp[i][j][k]);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}