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

2021-12-08 16:37:51

题目链接：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): 3289 Accepted Submission(s): 1144

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 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

Source

2013腾讯编程马拉松复赛第二场（3月30日）

题解：

POJ1185 炮兵阵地此题的变形。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e5;

 const int MAXN = 1e3+;

 int row[], sta[], cnt[], dp[][][];

 int main()

 {

     int n, m;

     while(scanf("%d%d", &n,&m)!=EOF)

     {

         for(int i = ; i<=n; i++)

         {

             int val;

             row[i] = ;

             for(int j = ; j<m; j++)

             {

                 scanf("%d", &val);

                 row[i] += (val==)*(<<j);

             }

         }

         int tot = ;

         for(int s = ; s<(<<m); s++)

         {

             if(!(s&(s<<)))

             {

                 sta[++tot] = s;

                 cnt[tot] = ;

                 for(int j = ; j<m; j++)

                     if(s&(<<j))

                         cnt[tot]++;

             }

         }

         memset(dp, , sizeof(dp));

         for(int i = ; i<=n; i++)

         {

             for(int j = ; j<=tot; j++)

             {

                 int s1 = sta[j];

                 if(i> && (s1&row[i-])) continue;

                 for(int k = ; k<=tot; k++)

                 {

                     int s2 = sta[k];

                     if(i> && (s2&row[i-])) continue;

                     if(s1&(s2<<) || (s1&(s2>>)) ) continue;

                     for(int t = ; t<=tot; t++)

                     {

                         int s3 = sta[t];

                         if(s3&row[i]) continue;

                         if(s2&(s3<<) || (s2&(s3>>)) ) continue;

                         if(s1&s3) continue;

                         dp[i][k][t] = max(dp[i][k][t], dp[i-][j][k]+cnt[t]);

                     }

                 }

             }

         }

         int ans = ;

         for(int i = ; i<=tot; i++)

             for(int j = ; j<=tot; j++)

                 ans = max(ans, dp[n][i][j]);

         printf("%d\n", ans);

     }

 }

码农公寓

郑厂长系列故事——排兵布阵

相关文章