POJ 1185(动态规划-状压dp)-蒲公英云

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

忘是亡心i 2022-06-01 11:13 288阅读 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的加强版点击打开链接，每一行用一个二进制数表示状态，我们发现转移状态的时候，需要知道前面俩行的状态，所以得用三维数组

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;
}