HDU 4539 郑厂长系列故事——排兵布阵 状压dp

题目链接:

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-----------------------------------------------------------------------
上一篇:hdu_4539_郑厂长系列故事——排兵布阵(状压DP|最大团)


下一篇:【虚拟化实战】VM设计之一vCPU