hdu4539 郑厂长系列故事——排兵布阵 + POJ1158 炮兵阵地
阅读原文时间:2023年07月08日阅读:4

**题意:

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

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 1883    Accepted Submission(s): 686

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

2

思路:

      说好了状态压缩dp的,自己dp写着特别费劲,写了一个,结果超时了,然后果断换思路,后来感觉可以直接求最大独立集,因为不能抽象能二分图,所以如果想求独立集,那么就只剩下一个比较暴力的np问题了,就是最大团,虽说是np问题,但是可以靠一些很实用的剪纸和简单dp来优化,这个题目还是轻松的过掉了,建图的时候把不冲突的两个点连接起来,最后一遍最大团就行了。同样的还有POJ1185 炮兵阵地,只是建图的时候的限制不一样而已,别的都一样,具体看代码,明明是在学习dp,怎么又写图论了。

#include

#include

#define N 1100

typedef struct

{

   int x ,y;

}NODE;

NODE node[N];

int map[N][N] ,n;

int dp[N] ,now[N];

int Ans;

void DFS(int s ,int sum)

{

   if(Ans < sum)  Ans = sum;

   int tnow[N] ,able = 0;

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

   {

      tnow[i] = now[i];

      if(now[i]) able ++;

   }

   if(able + sum < Ans) return;

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

   {

      if(!tnow[i]) continue;

      if(sum + dp[i] <= Ans) return;

      for(int j = s+1 ;j <= n ;j ++)

      now[j] = tnow[j] & map[i][j];

      DFS(i ,sum + 1);

   }

}

int Max_Tuan()

{

   dp[n] = Ans = 1;

   for(int i = n - 1 ;i >= 1 ;i --)

   {

      for(int j = 1 ;j <= n ;j ++)

      now[j] = map[i][j];

      now[i] = 1;

      DFS(i ,1);

      dp[i] = Ans;

   }

   return Ans;

}

int abss(int x)

{

   return x > 0 ? x : -x;

}

int ok(int a ,int b)

{

   int dis = abss(node[a].x - node[b].x) + abss(node[a].y - node[b].y);

   if(dis == 2) return 0;

   return 1;

}

int main ()

{

   int nn ,mm ,i ,j ,a;

   while(~scanf("%d %d" ,&nn ,&mm))

   {

      int nowid = 0;

      for(i = 1 ;i <= nn ;i ++)

      for(j = 1 ;j <= mm ;j ++)

      {

         scanf("%d" ,&a);

         if(!a) continue;

         nowid ++;

         node[nowid].x = i ,node[nowid].y = j;

      }

      if(!nowid)

      {

         printf("0\n");

         continue;

      }

      memset(map ,0 ,sizeof(map));

      for(i = 1 ;i <= nowid ;i ++)

      for(j = i + 1 ;j <= nowid ;j ++)

      map[i][j] = map[j][i] = ok(i ,j);

      n = nowid;

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

   }

   return 0;

}

POJ 1185

炮兵阵地

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 19703 Accepted: 7610

Description

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 

如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 

现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 

Input

第一行包含两个由空格分割开的正整数,分别表示N和M; 

接下来的N行,每一行含有连续的M个字符('P'或者'H'),中间没有空格。按顺序表示地图中每一行的数据。N <= 100;M <= 10。

Output

仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。

Sample Input

5 4

PHPP

PPHH

PPPP

PHPP

PHHP

Sample Output

6

Source

    

#include

#include

#define N 1100

typedef struct

{

   int x ,y;

}NODE;

NODE node[N];

int map[N][N] ,n;

int dp[N] ,now[N];

int Ans;

void DFS(int s ,int sum)

{

   if(Ans < sum)  Ans = sum;

   int tnow[N] ,able = 0;

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

   {

      tnow[i] = now[i];

      if(now[i]) able ++;

   }

   if(able + sum < Ans) return;

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

   {

      if(!tnow[i]) continue;

      if(sum + dp[i] <= Ans) return;

      for(int j = s+1 ;j <= n ;j ++)

      now[j] = tnow[j] & map[i][j];

      DFS(i ,sum + 1);

   }

}

int Max_Tuan()

{

   dp[n] = Ans = 1;

   for(int i = n - 1 ;i >= 1 ;i --)

   {

      for(int j = 1 ;j <= n ;j ++)

      now[j] = map[i][j];

      now[i] = 1;

      DFS(i ,1);

      dp[i] = Ans;

   }

   return Ans;

}

int abss(int x)

{

   return x > 0 ? x : -x;

}

int ok(int a ,int b)

{

    int xx = abss(node[a].x - node[b].x);

    int yy = abss(node[a].y - node[b].y);

    if(!xx && yy <= 2 || !yy && xx <= 2) return 0;

    return 1;

}

int main ()

{

   int nn ,mm ,i ,j ,a;

   char str[110];

   while(~scanf("%d %d" ,&nn ,&mm))

   {

      int nowid = 0;

      for(i = 1 ;i <= nn ;i ++)  

      {

         scanf("%s" ,str); 

         for(j = 1 ;j <= mm ;j ++)

         {

           

            if(str[j-1] != 'P') continue;

            nowid ++;

            node[nowid].x = i ,node[nowid].y = j;

         }

      }

      if(!nowid)

      {

         printf("0\n");

         continue;

      }

      memset(map ,0 ,sizeof(map));

      for(i = 1 ;i <= nowid ;i ++)

      for(j = i + 1 ;j <= nowid ;j ++)

      map[i][j] = map[j][i] = ok(i ,j);

      n = nowid;

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

   }

   return 0;

}**