洛谷P2704/NOI2001 炮兵阵地

@Pelom  September 26, 2019

题意:

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

example

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

数据范围: $N \le 100,M \le 10$

题解:

算法:状压dp

由于一个炮兵可以影响到其之后两行的放置,所以考虑状压两行状态。使用 $dp[i][j][k]$ 表示第 $i$ 行的状态编号为 $j$ ,且上一行的状态编号为 $k$ 。易得状态转移方程:

$$dp[i][j][k]=max(dp[i-1][k][l]+sum[j])$$

其中 $l$ 为上上行的状态编号, $sum[j]$ 为状态编号为 $j$ 的状态中所含的炮兵个数。

在读入时,将地图信息状态压缩,每行用 $0/1$ 表示 $P/H$ ,代码如下:

for(int i=1;i<=n;i++){
    scanf("%s",ch+1);
    for(int j=1;j<=m;j++)
        (f[i]<<=1)|=(ch[j]=='H');
}

先预处理出前两行的dp信息,保证对地图信息合法,并同时计数所有单行合法状态 $stt[]$ :

tot=(1<<m)-1;
for(int i=0;i<=tot;i++){
    if(i&(i<<1) || i&(i<<2))
        continue;
    stt[++cnt]=i;
    sum[cnt]=calc(i);
    if(i&f[1])
        continue;
    dp[1][cnt][0]=sum[cnt];
}
for(int i=1;i<=cnt;i++){
    int x=stt[i];
    for(int j=1;j<=cnt;j++){
        int y=stt[j];
        if(f[2]&y || x&y)
            continue;
        dp[2][j][i]=dp[1][i][0]+sum[j];
    }
}

接下来进行dp:

for(int i=3;i<=n;i++)
    for(int j=1;j<=cnt;j++){
        int x=stt[j];
        if(f[i]&x)
            continue;
        for(int k=1;k<=cnt;k++){
            int y=stt[k];
            if(x&y)
                continue;
            for(int l=1;l<=cnt;l++){
                int z=stt[l];
                if(x&z || y&z)
                    continue;
                dp[i][j][k]=Max(dp[i][j][k],dp[i-1][k][l]+sum[j]);
            }
        }
    }

因为当前行状态仅依赖于前两行,所以考虑滚动数组优化:

for(int i=3;i<=n;i++)
    for(int j=1;j<=cnt;j++){
        int x=stt[j];
        if(f[i]&x)
            continue;
        for(int k=1;k<=cnt;k++){
            int y=stt[k];
            if(x&y)
                continue;
            for(int l=1;l<=cnt;l++){
                int z=stt[l];
                if(x&z || y&z)
                    continue;
                dp[i%3][j][k]=Max(dp[i%3][j][k],dp[(i-1)%3][k][l]+sum[j]);
            }
        }
    }

最后统计答案即可。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
const int M=10;
int n,m;
int tot,cnt,ans;
char ch[M];
int f[N],stt[1<<M],sum[1<<M],dp[3][1<<M][1<<M];
template <typename T>
inline T Max(T a,T b){
    return a>b?a:b;
}
inline int calc(int x){
    int res=0;
    for(;x;x&=x-1)
        res++;
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++)
            (f[i]<<=1)|=(ch[j]=='H');
    }
    tot=(1<<m)-1;
    for(int i=0;i<=tot;i++){
        if(i&(i<<1) || i&(i<<2))
            continue;
        stt[++cnt]=i;
        sum[cnt]=calc(i);
        if(i&f[1])
            continue;
        dp[1][cnt][0]=sum[cnt];
    }
    for(int i=1;i<=cnt;i++){
        int x=stt[i];
        for(int j=1;j<=cnt;j++){
            int y=stt[j];
            if(f[2]&y || x&y)
                continue;
            dp[2][j][i]=dp[1][i][0]+sum[j];
        }
    }
    for(int i=3;i<=n;i++)
        for(int j=1;j<=cnt;j++){
            int x=stt[j];
            if(f[i]&x)
                continue;
            for(int k=1;k<=cnt;k++){
                int y=stt[k];
                if(x&y)
                    continue;
                for(int l=1;l<=cnt;l++){
                    int z=stt[l];
                    if(x&z || y&z)
                        continue;
                    dp[i%3][j][k]=Max(dp[i%3][j][k],dp[(i-1)%3][k][l]+sum[j]);
                }
            }
        }
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            ans=Max(ans,dp[n%3][i][j]);
    printf("%d",ans);
    return 0;
}

添加新评论