【NOI2001】炮兵陣地

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

6

題解

這題乍一看除了暴力之外都不太好下手，但是我們看到 M ≤ 10 M≤10 M≤10非常小，所以我們可以考慮將每一列進行狀壓（1表示放了炮兵部隊，0表示沒放），于是我們就可以設出一個很樸素的狀態：設 f [ i ] [ s 1 ] [ s 2 ] f[i][s1][s2] f[i][s1][s2]表示放完了第 i i i行，上一行的放置狀態為 s 1 s1 s1，上上行的放置狀態為 s 2 s2 s2時最多可以放的炮兵部隊的數量，
但是我們計算一下空間：大概是在400MB左右，在gmoj上可以過，但是在洛谷上就會MLE，所以我們考慮怎么縮減狀態，
通過寫暴力可以發現，在 m ≤ 10 m≤10 m≤10以內同一行的合法放置狀態不會超過60個，于是我們可以用一個 o k ok ok陣列存下在同一行內合法的狀態以及這樣狀態下可以在同一行內放置多少個炮兵部隊，便可以得到一個很簡潔的狀態：設 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示放完了第 i i i行，上一行的狀態是第 j j j個合法狀態，上上行的狀態是第 k k k個合法狀態時最多可以放的炮兵部隊的數量，于是做法就很顯然了
先將整個圖的狀壓，然后先預處理出第一行 f [ 1 ] f[1] f[1]的狀態出來，轉移的時候注意第二行要進行特殊處理，因為它前面只有一行，然后就可以愉快地暴力DP轉移了，

CODE

#include<cstdio>
#include<string>
#include<iostream>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 105
#define M 65 
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int map[N],ok[N],f[N][M][M],cnt,tot,oknum[N],ans,n,m;
inline void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
inline int count(int x)
{
	int t=0;
	while (x) {++t;x-=lowbit(x);}
	return t;
}
int main()
{
	read(n);read(m);
	for (R i=1;i<=n;++i)
	{
		char s[15];cin>>s;
		for (R j=0;j<=m;++j)
			if (s[j]=='H') map[i]|=1<<j;
	}
	tot=(1<<m)-1;
	for (R s=0;s<=tot;++s)
	{
		if (!(s&(s<<1)) && !(s&(s<<2)) && !(s&(s>>1)) && !(s&(s>>2)))
		{
			ok[++cnt]=s;oknum[cnt]=count(s);
			if (!(s&map[1])) f[1][0][cnt]=oknum[cnt];
		}
	}
	for (R i=1;i<=cnt;++i)
		for (R j=1;j<=cnt;++j)
			if (!(ok[i]&ok[j]) && !(ok[j]&map[2])) f[2][i][j]=max(f[2][i][j],f[1][0][i]+oknum[j]);
	for (R i=3;i<=n;++i)
		for (R j=1;j<=cnt;++j)
			if (!(map[i]&ok[j]))
				for (R k=1;k<=cnt;++k)
					if (!(ok[j]&ok[k]))
						for (R v=1;v<=cnt;++v)
							if (!(ok[v]&ok[k]) && !(ok[v]&ok[j])) f[i][k][j]=max(f[i][k][j],f[i-1][v][k]+oknum[j]);
	for (R i=1;i<=cnt;++i)
		for (R j=1;j<=cnt;++j)
			ans=max(ans,f[n][i][j]);
	printf("%d\n",ans);
	return 0;
}