【状压dp】hdu4539郑厂长系列故事——排兵布阵

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

http://acm.hdu.edu.cn/showproblem.php?pid=4539

问题描述：给你一个n行m列的0-1矩阵，0表示不能安置炮兵，1可以安置炮兵，要求炮兵的曼哈顿距离为2的位置不能有其他炮兵，问最多可安置炮兵的数目

思路： 状态压缩+位运算+动态规划

基本思路参考上一题

http://blog.csdn.net/u012717411/article/details/48898019

与上一题的区别在于曼哈顿距离为2，第i-1层对角线不能重复，第i-2层正对的不能重复，全部通过位运算解决，很好想，会前一题直到题就很简单，注意先把所有情况属枚举一遍确定范围，避免爆内存。

参考代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define pi acos(-1)
#define long long ll
#define M 10
#define N 110

using namespace std;

const int _max = 170 + 10;//最多可能状况不超169种,太大或MLE
const int mod = 1e8;

int x,n,m,row[N],top,st[_max];

int dp[N][_max][_max],cnt[_max];


bool judge(int x,int j){//自身地形合适
  int y = st[j];
  if(y&~x) return false;
  return true;
}

void init(){//状态压缩
  top=0;
  for(int i = 0; i <(1<    if(i&(i<<2)) continue;
    st[++top] = i;
    int t = i,res = 0;;
    while(t){
        if(t&1) res++;
        t>>=1;
    }
    cnt[top] = res;
  }
}

int main()
{
   #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   #endif // ONLINE_JUDGE
   while(~scanf("%d%d",&n,&m)){
    for(int i = 1; i <= n; ++ i){
        row[i] = 0;
        for(int j = 1; j <= m; ++ j){
          scanf("%d",&x);
          row[i]=(row[i]<<1)+x;
        }
    }
    init();
    memset(dp,0,sizeof(dp));
    for(int i = 1; i <= top;++ i)
        if(judge(row[1],i)) dp[1][i][1] = cnt[i];
    //dp
    for(int i = 2; i <= n; ++ i)
      for(int j = 1; j <= top; ++ j){
        if(!judge(row[i],j)) continue;//自己行地形合适
        for(int k =1; k<= top; ++ k){//i-1行状态
         if(st[j]&(st[k]<<1)) continue;
         if(st[j]&(st[k]>>1)) continue;
         for(int p = 1; p <= top; ++ p){//i-2行状态
            if(st[j]&st[p]) continue;
            if(st[k]&(st[p]<<1)) continue;
            if(st[k]&(st[p]>>1)) continue;
            dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][i==2?1:p]+cnt[j]);
         }
         }

      }
      int tar = -1;
      for(int i = 1; i <= top; ++ i)
        for(int j = 1;j <= top; ++ j)
          if(tar       printf("%d\n",tar);
   }
   return 0;
}

• 加粗 Ctrl + B
• 斜体 Ctrl + I
• 引用 Ctrl + Q
• 插入链接 Ctrl + L
• 插入代码 Ctrl + K
• 插入图片 Ctrl + G
• 提升标题 Ctrl + H
• 有序列表 Ctrl + O
• 无序列表 Ctrl + U
• 横线 Ctrl + R
• 撤销 Ctrl + Z
• 重做 Ctrl + Y