题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4539
郑厂长系列故事——排兵布阵
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
#### 问题描述
> 郑厂长不是正厂长
> 也不是副厂长
> 他根本就不是厂长
> 事实上
> 他是带兵打仗的团长
> 一天，郑厂长带着他的军队来到了一个n*m的平原准备布阵。
> 根据以往的战斗经验，每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置，同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
> 现在，已知n,m 以及平原阵地的具体地形，请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
输入
输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
输出
请为每组数据计算并输出最多能安排的士兵数量，每组数据输出一行。
样例输入
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
样例输出
2
题意
每个点会攻击离它哈密顿距离为2的所有点，以及它自己所在的点，现在给你一个n*m的棋盘，有些点上不能放棋子，问最多能放多少个棋子，且任意两个棋子都不会互相攻击。
题解
dp[cur][i][j]表示第cur-1行状态为i，第cur行状态为j，能装下的最大不冲突棋子数。
做法和[port]差不多
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=10000000000000000LL;
const double eps=1e-9;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=111;
const int maxm=11;
const int maxs=400;
LL dp[2][maxs][maxs];
int n,m;
///处理出有效状态
VI sta;
vector<LL> sumv;
void pre(){
for(int i=0;i<(1<<10);i++){
int cnt=0;
bool su=true;
for(int j=0;j<10;j++){
if(!(i&(1<<j))) continue;
cnt++;
if(j-2>=0&&(i&(1<<(j-2)))){ su=false; break; }
}
if(!su) continue;
sta.pb(i);
sumv.pb(cnt);
}
}
int tot;
int arr[maxn][maxm];
bool ok(int x,int i){
for(int j=0;j<m;j++){
if(!(x&(1<<j))) continue;
if(arr[i][j]==0) return false;
}
return true;
}
bool ok2(int pp,int p,int u){
for(int j=0;j<m;j++){
if(!(u&(1<<j))) continue;
if(j&&(p&(1<<(j-1)))) return false;
if(j<m-1&&(p&(1<<(j+1)))) return false;
if(pp>=0&&(pp&(1<<j))) return false;
}
return true;
}
void dealone(){
LL ans=0;
for(int i=0;i<tot;i++){
if(ok(sta[i],0)) ans=max(ans,sumv[i]);
}
prf("%lld\n",ans);
}
int main() {
pre();
while(scf("%d%d",&n,&m)==2) {
tot=upper_bound(all(sta),(1<<m)-1)-sta.begin();
// bug(tot);
rep(i,0,n) rep(j,0,m){
scf("%d",&arr[i][j]);
}
if(n==1){ dealone(); continue; }
int cur=0;
clr(dp[cur],0);
for(int i=0;i<tot;i++){
if(!ok(sta[i],0)) continue;
for(int j=0;j<tot;j++){
if(!ok(sta[j],1)) continue;
if(!ok2(-1,sta[i],sta[j])) continue;
dp[cur][i][j]=sumv[i]+sumv[j];
}
}
// bug(dp[cur][17][4]);
for(int t=2;t<n;t++){
cur^=1;
clr(dp[cur],0);
for(int k=0;k<tot;k++){
if(!ok(sta[k],t)) continue;
for(int j=0;j<tot;j++){
if(!ok(sta[j],t-1)) continue;
if(!ok2(-1,sta[j],sta[k])) continue;
for(int i=0;i<tot;i++){
if(!ok(sta[i],t-2)) continue;
if(!ok2(sta[i],sta[j],sta[k])) continue;
dp[cur][j][k]=max(dp[cur][j][k],dp[cur^1][i][j]+sumv[k]);
}
}
}
}
LL ans=0;
for(int i=0;i<tot;i++){
for(int j=0;j<tot;j++){
ans=max(ans,dp[cur][i][j]);
}
}
prf("%lld\n",ans);
}
return 0;
}
//end-----------------------------------------------------------------------