POJ 1185(动态规划-状压dp)

忘是亡心i 2022-06-01 11:13 173阅读 0赞

问题描述:

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

![ba1d4fa736b99550a7ee43784c287df9_v_1516863068][]

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

Input

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

Output

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

Sample Input

5 4
    PHPP
    PPHH
    PPPP
    PHPP
    PHHP

Sample Output

题目题意:题目给我们一个矩阵，有的地方可以放士兵，有的地方不可以，而且一个地方放了有些地方不能放（如图），最多放多少个士兵。

题目分析:这道题应该是POJ3524的加强版[点击打开链接][Link 1]，每一行用一个二进制数表示状态，我们发现转移状态的时候，需要知道前面俩行的状态，所以得用三维数组

dp\[cur\]\[i\]\[first\]cur表示当前行的状态，i表示当前行，first表示前面一行，保存最大值。转移的时候得判断三个状态相与为0.

我们首先得预处理每一行的可行状态，具体看一下代码就知道了，把该保存的先保存好。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    using namespace std;
    
    const int maxn=105;
    char G[105][15];
    vector<int> vec[maxn],num[maxn];
    int dp[250][105][250];
    int n,m,s;
    bool check(int x,int k)
    {
        s=0;
        if (k&(k<<1)) return false;
        if (k&(k<<2)) return false;
        for (int i=0;i<m;i++) {
            if (k&(1<<i)) {
                s++;
                if (G[x][i+1]=='H') return false;
            }
        }
        return true;
    }
    void init()
    {
        for (int i=1;i<=n;i++) {
            vec[i].clear();
            num[i].clear();
            for (int j=0;j<(1<<m);j++) {
                if (check(i,j)) {
                    vec[i].push_back(j);//保存状态
                    num[i].push_back(s);//保存每一个状态的1的数目
                }
            }
        }
    }
    int main()
    {
        while (scanf("%d%d",&n,&m)!=EOF) {
            for (int i=1;i<=n;i++) {
                scanf("%s",G[i]+1);
            }
            init();
            memset (dp,0,sizeof (dp));
            for (int i=0;i<vec[1].size();i++) {
                dp[i][1][i]=max(dp[i][1][i],num[1][i]);
            }
            int ans=0;
            if (n==1) {
                for (int i=0;i<vec[1].size();i++) {
                   ans=max(dp[i][1][i],ans);
                }
                printf("%d\n",ans);
                continue;
            }
            for (int i=2;i<=n;i++) {
                for (int j=0;j<vec[i].size();j++) {
                    if (i!=2) {
                       for (int l=0;l<vec[i-1].size();l++) {
                           for (int k=0;k<vec[i-2].size();k++){
                               if ((vec[i-1][l]&vec[i-2][k])!=0) continue;
                               if (((vec[i][j]&vec[i-2][k])==0)&&((vec[i][j]&vec[i-1][l])==0)) {
                                  dp[j][i][l]=max(dp[j][i][l],dp[l][i-1][k]+num[i][j]);
                                  ans=max(ans,dp[j][i][l]);
                               }
                           }
                       }
                    }
                    else {
                        for (int l=0;l<vec[i-1].size();l++) {//第二行判断特殊点，它前面只有一行
                            if ((vec[i][j]&vec[i-1][l])==0) {
                               dp[j][i][l]=max(dp[j][i][l],dp[l][i-1][l]+num[i][j]);
                               ans=max(ans,dp[j][i][l]);
                            }
                        }
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[ba1d4fa736b99550a7ee43784c287df9_v_1516863068]: https://odzkskevi.qnssl.com/ba1d4fa736b99550a7ee43784c287df9?v=1516863068
[Link 1]: http://blog.csdn.net/wust_cyl/article/details/79091165