HDOJ 4539 郑厂长系列故事——排兵布阵(状压DP)

10/19 10:56
阅读数 24

 

郑厂长系列故事——排兵布阵

TimeLimit: 10000/5000 MS (Java/Others)    Memory Limit:65535/32768 K (Java/Others)
Total Submission(s): 2839    Accepted Submission(s): 1009

 

Problem Description

  郑厂长不是正厂长
  也不是副厂长
  他根本就不是厂长
  事实上
  他是带兵打仗的团长

  一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。
  根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
  现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。







 

 

Input

输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n<= 100, m <= 10 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。

 

 

Output

请为每组数据计算并输出最多能安排的士兵数量,每组数据输出一行。

 

 

Sample Input

6 6

0 0 0 0 0 0

0 0 0 0 0 0

0 0 1 1 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

 

 

Sample Output

2

 

 

题意:中文题目,故题意不赘述。

分析:我们需要考虑三种不满足要求的情况

  1. 在相同一行距离为2(即相隔一列)的两个点都排布士兵
  2. 在相同一列距离为2(即相隔一行)的两个点都排布士兵
  3. 相邻行相邻列构成的1*1的正方形格子对角线上的两个点都排布士兵
  4. 不满足地形要求

对于每一行士兵排布的情况最大有2^10,数据比较大,所以适合用二进制数来表示(即状态压缩) 比如一个数x表示第i行的状态,则这个数的二进制表示中第几位有1就代表这一行的第几列排布了士兵,同时可以利用count()函数计算出某个状态中排布了多少士兵,num[x]=count(x).

下面给出利用二进制数来判断是否满足上面三个限制条件的方法(应该比较好理解)

  1. x&(x<<2)
  2. x&y
  3. x&(y<<1)||y&(x<<1)

PS:在下面的代码中,我用了mp[i]表示了某一行的地形限制情况。但我用1来表示了不能排布的位置,比如样例中的第3行,限制情况为001100,但我存的是110011,这是为什么?其实是为了方便用上面的x&y来判断我的排布是否满足地形限制,存的位置是0,我在这个位置排布士兵(即1),0&1=0,满足条件

dp[i][j][k]来表示计算到第i行,第i行的状态为j,i-1行的状态为k时,所能排布士兵的最大数目。通过遍历每一行的状态来进行更新。(这里在时间上可以有个优化,因为状态分别为【0,1<<n-1,这些状态中有的是不满足限制条件i的,故可提前筛除,即init()函数) 状态转移方程为dp[i][j][k] =max(dp[i][j][k], dp[i-1][k][t] + num[j]);

最后扫一遍最后一行对应所有状态的结果即可

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define f(i,a,b) for(int i=(a);i<(b);++i)
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn= 205;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;

int mp[maxn];
int state[maxn];
int num[maxn];
int dp[105][maxn][maxn];
int n,m;
int cnt;
 
bool one(int x)         //判断某一行的排列
{ 
    if(x&(x<<2))    return 0;
    return 1;
}

bool two(int x,int y)   //判断相隔一行的两行排列or判断是否满足地形限制
{
    if(x&y)     return 0;
    return 1;
}

bool next(int x,int y)   //判断相邻行的排列
{
    if(x&(y<<1)||y&(x<<1))  return 0;
    return 1;
}

int count(int x)       //求x的二进制表示中1的个数
{
    int sum = 0;
    while(x)
    {
        x&=(x-1);
        sum++;
    }
    return sum;
}

void init()
{
    mst(mp,0);
    cnt=0;
    int total=(1<<m);
    for(int i=0;i<total;i++)
    {
        if(one(i))
            state[cnt++]=i;
    }
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();               //处理出每一行所有可能的状态
        int x;
        for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            scanf("%d",&x);
            if(x==0)            //结合two()理解
                mp[i]+=(1<<j);
        }
        mst(dp,-1);
        //特殊处理第一行的排布
        for(int i=0;i<cnt;i++)
        {
            num[i]=count(state[i]);
            if(two(state[i],mp[1]))
            {
                for(int j=0;j<cnt;j++)   //如果满足地形的限制条件,则第三维的状态任意
                {
                    dp[1][i][j]=num[i];
                }
            }
        }
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j <cnt; j++)
            {
                if(!two(state[j], mp[i])) continue;   //该行是否满足地形限制
                for(int k = 0; k <cnt; k++)
                {
                    if(!next(state[j], state[k])) continue;   //相邻行
                    for(int t = 0; t <cnt; t++)
                    {
                        if(!two(state[t], state[j])) continue;  //相隔两行
                        if(dp[i-1][k][t] != -1)
                        {
                            dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][t] + num[j]);
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<cnt;i++)
        for(int j=0;j<cnt;j++)
        {
            ans=max(ans,dp[n][i][j]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

 

 

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部