Description
司令部的将軍們打算在NM的網格地圖上部署他們的炮兵部隊。一個NM的地圖由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
分析
看到資料很小，題目比較難，得出做法：狀壓DP
輸入高山平原的時候需要預處理，把地形轉化為01并壓縮到map數組裡面。
然後枚舉每一行的狀态，并且判斷這一行是否為合法狀态。判斷的方法就是在s變量（用于計算間隔）等于0之前又遇到一個1那就是不合法。如果等于0的時候遇到一個1那就把s變為3。s是每次-1的。
判斷合法的一行狀态就可以累加tot，表示真實用于DP的狀态的數量，可以有效壓縮數組空間。
然後開始DP。
我們設 f [ i ] [ l ] [ k ] f[i][l][k] f[i][l][k]為第 i i i行有 l l l點貢獻（放了 l l l個炮兵），上一行（ i − 1 i-1 i−1行）有 k k k點貢獻。
狀态轉移方程： f [ i ] [ l ] [ k ] = m a x ( f [ i ] [ l ] [ k ] , f [ i − 1 ] [ k ] [ j ] + n u m [ l ] ) ; f[i][l][k]=max(f[i][l][k],f[i-1][k][j]+num[l]); f[i][l][k]=max(f[i][l][k],f[i−1][k][j]+num[l]);
這裡其實 j j j表示i-2行的貢獻，是以也要枚舉1層循環。
同時，不僅要判斷間隔，還要判斷是否為山地（map數組）。
上代碼
107行代碼47行括号。。。别問我為什麼那麼熱愛括号。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int n,m,map[1001],a[1<<10],num[1<<10],tot,ans;
int lowbit(int x)
{
return x&(-x);
}
bool check(int x)
{
int s=0;
while(x)//x這個二進制數已經表示了一行的狀态！
{
if((x&1)&&s!=0)//間距沒到3又出現一個1，是以判斷為不合法狀态
{
return false;
}
if(x&1)//如果這個值為1但是s減到0了，那證明間距是3或以上
{
s=3;
}
if(s!=0)
{
s--;
}
x=x>>1;//一行中某一位判斷完畢
}
return true;
}
int ask(int x)
{
int s=0;
for(;x>0;x-=lowbit(x))
{
s++;
}
return s;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char x;
cin>>x;
if(x=='P')
{
map[i]=(map[i]<<1);//直接左移就是标0
}
else
{
map[i]=(map[i]<<1)+1;//左移一位再加一就标上了1
}
}
}
for(int i=0;i<=(1<<m)-1;i++)
{
if(check(i))
{
tot++;//算真實要用于DP的數字有多少，表示有哪幾行是合法的
a[tot]=i;
num[tot]=ask(i);
}
}
int f[110][tot+1][tot+1];//f數組開101直接WA，要開大一點！！！！
for(int i=1;i<=n;i++)
{
for(int j=1;j<=tot;j++)
{
if((a[j]&map[i-2])==0)
{
for(int k=1;k<=tot;k++)
{
if((a[j]&a[k])==0&&(a[k]&map[i-1])==0)
{
for(int l=1;l<=tot;l++)
{
if((a[j]&a[l])==0&&(a[k]&a[l])==0&&(a[l]&map[i])==0)
{
f[i][l][k]=max(f[i][l][k],f[i-1][k][j]+num[l]);
}
}
}
}
}
}
}
for(int i=1;i<=tot;i++)//目前行的貢獻(炮兵數量)
{
for(int j=1;j<=tot;j++)//上一行的貢獻
{
ans=max(ans,f[n][i][j]);//n就是DP枚舉到第n行
}
}
cout<<ans;
return 0;
}
括号永遠滴神！！！