HDU-4539郑厂长系列故事——排兵布阵（状态压缩，动态规划）
HDU-4539郑厂长系列故事——排兵布阵（状态压缩，动态规划）
郑厂长系列故事——排兵布阵
Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 9 Accepted Submission(s) : 1 Font: Times New Roman | Verdana | Georgia Font Size: ← → 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
这一题和poj-1185，几乎一样的， http://blog.csdn.net/Dacc123/article/details/50318887 看懂这篇，这个就会做了，
关于位运算 http://blog.csdn.net/Dacc123/article/details/50974579
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
int n,m;
int a[105][15];
int dp[105][205][205];
int cnt;
int s[205];
int map[205];
int get(int x,int row)
{
int res=0;
int i=0;
int t=0;
while(x)
{
if(res=(x&1))
t++;
if(res&&a[row][i]==0)
return -1;
x>>=1;
i++;
}
return t;
}
bool ok(int x)
{
if(x&(x<<2)) return false;
return true;
}
void init()
{
memset(s,0,sizeof(s));
for(int i=0;i<(1<<m);i++)
{
if(ok(i))
{
s[cnt++]=i;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)
map[i]|=(1<<j);
}
}
cnt=0;
init();
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=0;j<cnt;j++)//当前这一行的状态
{
if(get(s[j],i)==-1)//当前状态不符合
continue;
if(i==0)
{
dp[0][j][0]=max(dp[0][j][0],get(s[j],i));
continue;
}
for(int v=0;v<cnt;v++)//i-1行的状态
{
if(get(s[v],i-1)==-1)//当前状态不符合地图
continue;
if((s[j]&(s[v]<<1))||(s[j]&(s[v]>>1)))//当前状态处于下一行的曼哈顿的距离
continue;
if(i==1)
{
dp[i][j][v]=max(dp[i][j][v],get(s[j],i)+dp[i-1][v][0]);
continue;
}
for(int k=0;k<cnt;k++)//i-2行的状态
{
if(s[j]&s[k])//i行处于i-2行的曼哈顿距离中
continue;
if((s[v]&(s[k]<<1))||(s[v]&(s[k]>>1)))//i-1行处于i-2行的曼哈顿距离
// continue;
if(get(s[k],i-2)==-1)//当前状态不符合地图
continue;
dp[i][j][v]=max(dp[i][j][v],dp[i-1][v][k]+get(s[j],i));
}
}
}
}
int ans=0;
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
{
ans=max(ans,dp[n-1][i][j]);
}
}
printf("%d\n",ans);
}
return 0;
}