状态压缩经典题目（poj1184 nyoj81）

深碍√TFBOYSˉ_ 2022-08-27 02:27 116阅读 0赞

题目描述：

描述

司令部的将军们打算在N\*M的网格地图上部署他们的炮兵部队。一个N\*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：  
![1185_1.jpg][]  
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。  
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

分析：这个题目有个简化版本 poj3254 ，觉得这个有难度的可以先做一下那个题目。

首先我们求的是最多能放多少个炮兵，那么假如我把所有的情况都枚举了，然后在得到的结果里面找一个最大值，那么是不是就可以了。其实这个题目的思想就是这么简单。

但是我们如果用一般的枚举的方法肯定会超时，那么就用到了状态压缩。

因为这个题目中一个炮影响的是两行，所以我们要多定义一维的状态来表示当前行的上上一行的状态。

状态：dp【i】【j】【k】 第 i 行，状态为 k ，第 i-1 行状态为 j 的最大放的炮兵数目；

转移方程 dp \[ i \] \[ k \] \[ t \] = max ( dp \[ i \] \[ k \] \[ t \] , dp \[ i - 1 \] \[ j \] \[ k \] + num \[ t \] );

代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define Max(a,b) a>b?a:b
    int N,M;
    char num[110],top;
    int stk[70],cur[110];
    int dp[110][70][70];
    
    bool judge1(int x)  //判断二进制有没有相邻的1 或者相隔2位
    {
        if((x&(x<<1)) || (x&(x<<2)))
            return false;
        return true;
    }
    bool judge2(int i,int x)
    {
        return (cur[i]&stk[x]);
    }
    void jinit()
    {
        top=0;
        int i,total=1<<N;
        for(i=0; i<total; i++) if(judge1(i)) stk[++top]=i;
    }
    int jcount(int x)
    {
        int cnt=0;
        while(x)
        {
            if(x&1)
                cnt++;
            x>>=1;
        }
        return cnt;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&M,&N);
            jinit();
            char x;
            int ans=0;
            for(int i = 1; i <= M; i++)
            {
                getchar();
                cur[i]=0;
                for(int j=1; j<=N; j++)
                {
                    scanf("%c",&x);
                    if(x=='H')
                        cur[i]+=(1<<(j-1));
                }
            }
            memset(dp,-1,sizeof(dp));
            for(int i = 1; i <= top; i++)
            {
                num[i]=jcount(stk[i]);
                if(!judge2(1,i))
                {
                    dp[1][1][i]=num[i];
                    ans=Max(ans,num[i]);
                }
            }
            int i,t,j,k;
            for(i = 2; i <= M; i++)
            {
                for(t = 1; t <= top; t++)  ///当前行
                {
                    if(judge2(i,t)) continue;
                    for(j = 1; j <= top; j++)  ///上上行
                    {
                        if(stk[t]&stk[j])continue;
                        for(k = 1; k <= top; k++)  ///上一行
                        {
                            if(stk[t]&stk[k])continue;
                            if(dp[i-1][j][k]==-1)continue;
                            dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]);
                            ans = Max(ans,dp[i][k][t]);
                        }
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[1185_1.jpg]: /images/20220824/e232917e49784c71af231bf717c0d7d0.png