原題地址說(shuō)實(shí)話我第一次嘗試寫(xiě)炮兵陣地是在2009年……已經(jīng)過(guò)去兩年多了，終于找到了一個(gè)好的解法……慶祝一下……
【狀態(tài)壓縮DP】
所謂狀態(tài)壓縮DP，就是對(duì)于某些DP問(wèn)題，每一階段的狀態(tài)都有很多維，要利用某些手段將它們壓縮到一維（一個(gè)正整數(shù)），順便進(jìn)行狀態(tài)的精簡(jiǎn)（去掉不合法的狀態(tài)），然后再進(jìn)行DP。這里講的主要是傳統(tǒng)的狀壓DP，有一種基于“插頭”的DP，更高級(jí)，以后再搞。
對(duì)于本題，可以設(shè)計(jì)出一個(gè)這樣的狀態(tài)：[0..1][0..1][0..1]...[0..1]（有M個(gè)[0..1]），表示該行的每個(gè)格子放不放炮兵，如果放，為1，否則為0。顯然，這是一個(gè)M位二進(jìn)制數(shù)，如果能把它們壓縮成一個(gè)int就好了。
【如何壓縮】
第一個(gè)問(wèn)題是這么多維的狀態(tài)如何壓縮的問(wèn)題。
對(duì)于本題，由于是二進(jìn)制數(shù)，直接壓縮就可以了。但是對(duì)于某些情況，狀態(tài)是個(gè)三進(jìn)制數(shù)（每個(gè)格子的屬性都有3種）甚至更多進(jìn)制數(shù)，這樣，直接壓縮會(huì)導(dǎo)致無(wú)法使用位運(yùn)算，從而使“解壓”變得很麻煩，耗時(shí)也很長(zhǎng)（需要暴力），因此，可以將每位三進(jìn)制都拆成兩位二進(jìn)制：
0->00
1->01
2->10
（當(dāng)然1拆成10、2拆成11也木有問(wèn)題，只要能區(qū)分開(kāi)就行了）
這樣，每個(gè)狀態(tài)就可以用2個(gè)二進(jìn)制數(shù)來(lái)表示，可以在構(gòu)造出所有合法狀態(tài)以后將每個(gè)狀態(tài)所對(duì)應(yīng)的兩位二進(jìn)制數(shù)存到struct里面，使用時(shí)調(diào)出即可。
【如何精簡(jiǎn)】
這個(gè)問(wèn)題是最重要的，因?yàn)椋绻痪?jiǎn)，在枚舉狀態(tài)以及轉(zhuǎn)移的時(shí)候就會(huì)枚舉到很多不合法狀態(tài)，導(dǎo)致時(shí)間浪費(fèi)。
所謂精簡(jiǎn)，是指在預(yù)處理以及DP過(guò)程中，盡量避開(kāi)不合法狀態(tài)。
（1）預(yù)處理中的精簡(jiǎn)：
包括3個(gè)部分：
<1>找到所有可能的合法狀態(tài)并編號(hào)：根據(jù)題意限制，有的狀態(tài)在階段內(nèi)就不合法（比如本題，一行一階段，那么凡是有兩個(gè)1位的距離小于2的狀態(tài)都不合法），而且這種狀態(tài)所占的比重往往還很大（本題中，M=10時(shí)，也只有60種可能的合法狀態(tài)），此時(shí)，為了找到這些合法狀態(tài)，可以DFS構(gòu)造實(shí)現(xiàn)。
需要注意的是，有的題不光要找到一個(gè)階段內(nèi)的合法狀態(tài)，還要找到兩個(gè)或兩個(gè)以上階段內(nèi)的合法狀態(tài)（比如那個(gè)有關(guān)多米諾骨牌的題），此時(shí)需要兩個(gè)int同時(shí)DFS；
在找到合法狀態(tài)以后，需要對(duì)每個(gè)合法狀態(tài)進(jìn)行編號(hào)，以達(dá)到“壓縮”的目的。這里就涉及到了狀態(tài)編號(hào)和狀態(tài)表示的問(wèn)題：比如，狀態(tài)1001，表示為9，在DFS中第一個(gè)被搜到，因此編號(hào)為0，不要搞混了這兩個(gè)（尤其不要搞混“編號(hào)為0”和“狀態(tài)表示為0”，它們是不同的）。在預(yù)處理和DP的過(guò)程中，所有涉及到狀態(tài)的數(shù)組下標(biāo)，全部是編號(hào)而不是表示，知道編號(hào)要求表示，可以在DFS中記錄的數(shù)組里面調(diào)，而知道表示要求編號(hào)，可以利用逆數(shù)組或者哈希；
<2>找到每一階段的合法狀態(tài)：即使是<1>中被判定為合法的狀態(tài)，在具體的各個(gè)階段中也未必合法（比如本題，如果某一行的某一個(gè)位置是'H'，不能放，而某一個(gè)狀態(tài)在這里放了，則不合法），因此要對(duì)每個(gè)階段再枚舉一遍，找到真正合法的狀態(tài)，并計(jì)入一個(gè)vector；
<3>找到狀態(tài)轉(zhuǎn)移中的合法狀態(tài)：在狀態(tài)轉(zhuǎn)移中，往往要求狀態(tài)不沖突（比如本題，在連續(xù)的三個(gè)階段中，都不能有某一位有兩個(gè)為1的情況），因此，還要枚舉每個(gè)狀態(tài)在轉(zhuǎn)移時(shí)與其不沖突的狀態(tài)，并計(jì)入vector。
注意，有時(shí)候這一步不是很容易進(jìn)行，需要在DP過(guò)程中進(jìn)行；
（2）DP過(guò)程中的精簡(jiǎn)：
DP過(guò)程中，枚舉狀態(tài)、轉(zhuǎn)移決策都只枚舉合法的，在vector里面調(diào)（注意vector里記錄的全都是狀態(tài)編號(hào)而不是表示！），可以大大減少枚舉量，不過(guò)有時(shí)候，還會(huì)有一些時(shí)間浪費(fèi)，這時(shí)候，可以采取一些其它的辦法來(lái)精簡(jiǎn)，比如再次進(jìn)行DFS構(gòu)造合法狀態(tài)等。
總之，這類(lèi)問(wèn)題的目標(biāo)就是“精簡(jiǎn)，精簡(jiǎn)，再精簡(jiǎn)，使枚舉到的不合法狀態(tài)減到最少”。
代碼：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define pb push_back
#define IR iterator
typedef vector <int> vi;
const int MAXN = 103, MAXM = 11, MAXS = 100, INF = ~0U >> 2;
int n, m, S, A[MAXN], B[MAXS], T1[MAXS], F[MAXN][MAXS][MAXS], res;
bool F0[MAXN][MAXS];
vi P0[MAXN], P1[MAXS][MAXS];
void init()
{
scanf("%d%d", &n, &m); getchar();
re1(i, n) {A[i] = 0; re(j, m) A[i] |= ((getchar() == 'P') << j); getchar();}
}
void dfs(int v, int ST)
{
if (v >= m) B[S++] = ST; else {dfs(v + 3, ST | (1 << v)); dfs(v + 1, ST);}
}
void prepare()
{
S = 0; dfs(0, 0);
re(i, S) {T1[i] = 0; for (int j=B[i]; j; j-=j&(-j)) T1[i]++;}
re1(i, n) re(j, S) if (!(~A[i] & B[j])) {P0[i].pb(j); F0[i][j] = 1;} P0[0].pb(S - 1); F0[0][S - 1] = 1;
re(i, S) re(j, S) if (!(B[i] & B[j])) re(k, S) if (!(B[i] & B[k]) && !(B[j] & B[k])) P1[i][j].pb(k);
}
void solve()
{
re3(i, 0, n) re(j1, S) re(j2, S) F[i][j1][j2] = -INF; F[0][S - 1][S - 1] = 0;
vi::IR vi_e0, vi_e1, vi_e2; int j0, j1, k, V;
re(i, n) {
vi_e0 = P0[i].end(); if (i) vi_e1 = P0[i - 1].end(); else vi_e1 = P0[i].end();
for (vi::IR p=P0[i].begin(); p != vi_e0; p++)
for (vi::IR p_=P0[i ? i - 1 : i].begin(); p_ != vi_e1; p_++) {
j0 = *p; j1 = *p_;
if (!(B[j0] & B[j1])) {
vi_e2 = P1[j0][j1].end();
for (vi::IR p__ = P1[j0][j1].begin(); p__ != vi_e2; p__++) {
k = *p__;
if (F0[i + 1][k]) {
V = F[i][j0][j1] + T1[k];
if (V > F[i + 1][k][j0]) F[i + 1][k][j0] = V;
}
}
}
}
}
res = 0; re(i, S) re(j, S) if (F[n][i][j] > res) res = F[n][i][j];
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}