首页 > 代码库 > HDU 4539 郑厂长系列故事——排兵布阵
HDU 4539 郑厂长系列故事——排兵布阵
http://acm.hdu.edu.cn/showproblem.php?pid=4539
郑厂长系列故事——排兵布阵
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1708 Accepted Submission(s): 620
Problem Description
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。
根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。
根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
Input
输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。
每组数据的第一行包含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
分析:曼哈顿距离为2,一个米,点就是中心,距离都是2,跟poj1181一样,稍微改一下就行。数组开大一点。int dp[102][202][202];
数组开得太小,一直wa,伤心了
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[102][202][202];int n,m,p,sta[4096],sum[4096];int count(int n) { int num = 0; while(n){ n &= (n - 1); num++; } return num; }void init(){ int i; for(i=0;i<1<<m;i++) { if((i<<2)&i) continue; sum[p]=count(i); sta[p++]=i; }}int fit(int x,int y){ if(x&y) return 0; else return 1;}int match(int x,int y){ if((x<<1)&y) return 0; if(x>>1&y) return 0; return 1;} int main() { int i,j,a[105],tem,k,r; while(~scanf("%d%d",&n,&m)) { p=0; memset(dp,-1,sizeof(dp)); memset(a,0,sizeof(a)); memset(sta,0,sizeof(sta)); memset(sum,0,sizeof(sum)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&tem); if(tem==0) a[i]+=1<<m-j; } } init(); for(i=0;i<p;i++) { if(fit(sta[i],a[1])) { dp[1][i][0]=sum[i]; } } for(i=2;i<=n;i++) { for(j=0;j<p;j++) { if(!fit(sta[j],a[i])) continue; for(k=0;k<p;k++) { if(!fit(sta[k],a[i-1])) continue; if(!match(sta[j],sta[k])) continue; for(r=0;r<p;r++) { if(!fit(sta[r],sta[j])) continue; if(!fit(sta[r],a[i-2])) continue; if(!match(sta[k],sta[r])) continue; dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][r]+sum[j]); } } } } int ans=0; for(i=0;i<p;i++) for(j=0;j<p;j++) { ans=max(ans,dp[n][i][j]); } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。