題意：


? ? ? ? ? ? ? ? ?鄭廠長系列故事——排兵布陣
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;
}
? ??
? ??
??
? ? ??
? ? ??
? ? ? ? ?
? ?
? ? ??
? ? ??

總結

以上是生活随笔為你收集整理的hdu4539 郑厂长系列故事——排兵布阵 + POJ1158 炮兵阵地的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。