题意：
郑厂长系列故事——排兵布阵
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<stdio.h>
#include<string.h>
#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<stdio.h>
#include<string.h>
#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;
}
相关文章
- HDU 4539 郑厂长系列故事——排兵布阵 —— 状压DP
- 郑厂长系列故事——排兵布阵 hdu4539（状态压缩DP）
- HDU 4539 郑厂长系列故事――排兵布阵(曼哈顿距离)
- POJ 1185 - 炮兵阵地 & HDU 4539 - 郑厂长系列故事——排兵布阵 - [状压DP]
- hdu_4539_郑厂长系列故事——排兵布阵(状压DP|最大团)
- HDU 4539 郑厂长系列故事——排兵布阵 状压dp
- HDU 4539 郑厂长系列故事——排兵布阵
- HDU 4539郑厂长系列故事――排兵布阵（状压DP）
- hdu4539 郑厂长系列故事——排兵布阵 + POJ1158 炮兵阵地
- [状压dp]HDOJ4539 郑厂长系列故事——排兵布阵