当前位置:网站首页>P2704 [NOI2001]炮兵阵地

P2704 [NOI2001]炮兵阵地

2021-06-25 08:36:19 圩纥

题目描述

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

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

输入输出格式

输入格式:

第一行包含两个由空格分割开的正整数,分别表示N和M;

接下来的N行,每一行含有连续的M个字符(‘P’或者‘H’),中间没有空格。按顺序表示地图中每一行的数据。N≤100;M≤10。

输出格式:

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

输入输出样例

输入样例#1: 
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
输出样例#1: 
6

 

Solution:

  本题状压dp水题

  定义$f[i][j][k]$表示前$i$行最后两行状态为$j,k$的最大放置数(第一维显然可以滚掉)。

  先预处理出单行的合法状态和放置部队数,然后转移时就二进制捣鼓一下判断合法(注意特判第一行的情况),最后枚举后两行的状态,求最大值就好了。

代码:

/*Code by 520 -- 10.17*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int M=11;
int n,m,cnt,f[2][1<<M][1<<M],mp[105],w[1<<M];
bool sta[1<<M];

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m; char c; int lim=(1<<m)-1;
    For(i,0,lim) {
        if((i<<1)&i||(i<<2)&i) continue;
        if((i>>1)&i||(i>>2)&i) continue;
        For(j,0,m-1) if(i&(1<<j)) w[i]++;
        sta[i]=1;
    }
    For(i,1,n) For(j,1,m) cin>>c,mp[i]+=(c=='P'?(1<<j-1):0);
    For(i,1,n) {
        For(j,0,lim) if(sta[j]&&((j&mp[i-1])==j)){
            For(k,0,lim)
                if(sta[k]&&(i==1||(k&mp[i-2])==k)&&(!(j&k)))
                For(p,0,lim) if(sta[p]&&(!(p&k))&&(!(p&j))&&(p&mp[i])==p)
                    f[cnt^1][j][p]=max(f[cnt^1][j][p],f[cnt][k][j]+w[p]);
            }
        cnt^=1;
    }
    int ans=0;
    For(i,0,lim) if(sta[i]&&(i&mp[n-1])==i)
    For(j,0,lim) if(sta[j]&&(j&mp[n])==j&&!(i&j)) ans=max(ans,f[cnt][i][j]);
    cout<<ans;
    return 0;
}

 

 
 
 

版权声明
本文为[圩纥]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15180869/2798650