炮兵陣地
| Time Limit: 2000MS | Memory Limit: 65536K |
| Total Submissions: 26426 | Accepted: 10185 |
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 題目連結：POJ 1185
以前一直想做來着，寫了ZOJ上的Firenet以為這是個差不多的二分比對，可惜連樣例都過不了（這就非常尴尬了）後來發現不一定是二分圖，後來發現是普通圖求最大獨立集，照着别人的最大獨立集模版寫了一個過了，然而現在也不會最大獨立集…………
改了一個下午的狀壓DP，結果連樣例都過不了，因為裡面的細節錯誤實在是太多，晚上删了重新寫就1A了……
用$dp[i][j][k]$表示目前第$i$行，第$j$種狀态（為什麼是種而不是直接的二進制轉換十進制$j$後面會講）且前一行的狀态為$k$。
顯然由狀壓基本法可以推出：$dp[i][j][k]=max(dp[i][j][k],dp[i-1][第i-1行的第j'個狀态][第i-2行的第k'個狀态]+cnt[j]$。
但是由于$m<=10$，如果用普通的二進制再轉十進制，DP數組則變成了$N*(1<<M)*(1<<M)$有1E多了，直接MLE，然後學習一下大牛的做法，先把所有可能的狀态預處理出來，然後用i代表示在預處理的狀态中第$i$個狀态，這樣一來狀态就隻有最多60種了（假設M=10且全部都是平原，則狀态總數剛好就是60），再用$cnt[i]$表示第i種狀态擺了幾個，還是偷懶用$bitset::count$就行了，對于平原和山地的處理，把平原看成1把山地看成0雖然便于了解，但是判斷起來不友善，是以要反過來把山地H看成1，若山地為1一旦有一個炮兵位置為1，則結果肯定不為0，這樣判斷是否安放了炮兵在山地上就很簡單了，然後就是按照以前的思路，多一個for處理第$i-2$行的狀态即可，一些坑點注釋在代碼裡了
代碼：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=105;
const int M=12;
const int S=65;
char pos[N][M];
int dp[N][S][S];
int row_bid[N];
int sta[S],cnt[S],tot,n,m;
inline bool check(const int &a,const int &b)
{
return (a&b)==0;
}
void init()
{
CLR(dp,0);
int R=1<<m;
tot=0;
for (int i=0; i<R; ++i)
{
if(check(i,i<<1)&&check(i,i<<2))
{
sta[tot]=i;
cnt[tot]=(int)bitset<11>(i).count();
++tot;
}
}
}
int main(void)
{
int i,j,k,p;
while (~scanf("%d%d",&n,&m))
{
init();//數組初始化以及預處理出本身就合法的狀态
for (i=0; i<n; ++i)
{
scanf("%s",pos[i]);
int temp=0;
for (j=0; j<m; ++j)
{
temp<<=1;
temp=temp+(pos[i][j]=='H');//這裡加個括号，否則先算+号再算==号就出問題了
}
row_bid[i]=temp;
}
//第一行初始化
for (i=0; i<tot; ++i)
{
if(check(sta[i],row_bid[0]))
dp[0][i][0]=cnt[i];
}
//第二行初始化
for (i=0; i<tot; ++i)//目前行(1)
{
if(check(sta[i],row_bid[1]))
{
for (j=0; j<tot; ++j)//上一行(0)
{
if(check(sta[j],row_bid[0])&&check(sta[i],sta[j]))
{
dp[1][i][j]=max<int>(dp[1][i][j],dp[0][j][0]+cnt[i]);
}
}
}
}
//後面進行DP
for (i=2; i<n; ++i)//每一行
{
for (j=0; j<tot; ++j)//目前行
{
if(check(row_bid[i],sta[j]))
{
for (k=0; k<tot; ++k)//上一行
{
if(check(row_bid[i-1],sta[k])&&check(sta[j],sta[k]))
{
for (p=0; p<tot; ++p)//上上行
{
if(check(row_bid[i-2],sta[p])&&check(sta[k],sta[p])&&check(sta[j],sta[p]))
{
dp[i][j][k]=max<int>(dp[i][j][k],dp[i-1][k][p]+cnt[j]);
}
}
}
}
}
}
}
int maxm=0;
for (i=0; i<tot; ++i)
for (j=0; j<tot; ++j)
if(dp[n-1][i][j]>maxm)
maxm=dp[n-1][i][j];
printf("%d\n",maxm);
}
return 0;
}
轉載于:https://www.cnblogs.com/Blackops/p/6009313.html