首页 > 代码库 > HDU4539:郑厂长系列故事——排兵布阵(状态压缩)

HDU4539:郑厂长系列故事——排兵布阵(状态压缩)

2024-07-02 09:22:23   220人阅读

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 60 0 0 0 0 00 0 0 0 0 00 0 1 1 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0
 

Sample Output
2
 
 
 
比较简单的状态压缩
 
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int map[105][15];int dp[1<<10][1<<10],tem[1<<10][1<<10];int now[1<<10],pre[1<<10],prepre[1<<10],ans[1<<10];int l_now,l_pre,l_prepre;int n,m;void dfs(int id,int k,int p,int sum){    if(k>=m)    {        now[++l_now] = p;        ans[l_now] = sum;        return;    }    if(k>=2 && map[id][k] && !(p&(1<<(k-2))))//这格可以放，而左边第二格不能放，那么在这个位置放下        dfs(id,k+1,p|(1<<k),sum+1);    else if(k<2 && map[id][k])//如果是前两列，这格可以放就先放下        dfs(id,k+1,p|(1<<k),sum+1);    dfs(id,k+1,p,sum);//这格不放}void solve(){    int i,j,k,t;    tem[1][1] = pre[1] = prepre[1] = 0;    l_now = l_pre = l_prepre = 1;    for(k = 0; k<n; k++)    {        l_now = 0;        dfs(k,0,0,0);        for(i = 1; i<=l_now; i++)            for(j = 1; j<=l_pre; j++)                dp[i][j] = 0;        for(i = 1; i<=l_now; i++)        {            for(j = 1; j<=l_pre; j++)            {                for(t = 1; t<=l_prepre; t++)                {                    if(now[i] & prepre[t]) continue;                    if(now[i] & (pre[j]>>1)) continue;                    if(now[i] & (pre[j]<<1)) continue;                    dp[i][j] = max(dp[i][j],tem[j][t]+ans[i]);                }            }        }        for(i = 1; i<=l_now; i++)            for(j = 1; j<=l_pre; j++)                tem[i][j] = dp[i][j];        for(i = 1; i<=l_pre; i++)            prepre[i] = pre[i];        for(i = 1; i<=l_now; i++)            pre[i] = now[i];        l_prepre = l_pre;        l_pre = l_now;    }}int main(){    int i,j;    while(~scanf("%d%d",&n,&m))    {        for(i = 0; i<n; i++)            for(j = 0; j<m; j++)                scanf("%d",&map[i][j]);        solve();        int maxn = 0;        for(i = 1; i<=l_pre; i++)            for(j = 1; j<=l_prepre; j++)                maxn = max(maxn,tem[i][j]);        printf("%d\n",maxn);    }    return 0;}

HDU4539:郑厂长系列故事——排兵布阵(状态压缩)


联系
我们