题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4539
郑厂长系列故事——排兵布阵
问题描述
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天，郑厂长带着他的军队来到了一个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 printftypedef 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-----------------------------------------------------------------------