原題地址說實話我第一次嘗試寫炮兵陣地是在2009年……已經過去兩年多了，終于找到了一個好的解法……慶祝一下……
【狀態壓縮DP】
所謂狀態壓縮DP，就是對于某些DP問題，每一階段的狀態都有很多維，要利用某些手段將它們壓縮到一維（一個正整數），順便進行狀態的精簡（去掉不合法的狀態），然后再進行DP。這里講的主要是傳統的狀壓DP，有一種基于“插頭”的DP，更高級，以后再搞。
對于本題，可以設計出一個這樣的狀態：[0..1][0..1][0..1]...[0..1]（有M個[0..1]），表示該行的每個格子放不放炮兵，如果放，為1，否則為0。顯然，這是一個M位二進制數，如果能把它們壓縮成一個int就好了。
【如何壓縮】
第一個問題是這么多維的狀態如何壓縮的問題。
對于本題，由于是二進制數，直接壓縮就可以了。但是對于某些情況，狀態是個三進制數（每個格子的屬性都有3種）甚至更多進制數，這樣，直接壓縮會導致無法使用位運算，從而使“解壓”變得很麻煩，耗時也很長（需要暴力），因此，可以將每位三進制都拆成兩位二進制：
0->00
1->01
2->10
（當然1拆成10、2拆成11也木有問題，只要能區分開就行了）
這樣，每個狀態就可以用2個二進制數來表示，可以在構造出所有合法狀態以后將每個狀態所對應的兩位二進制數存到struct里面，使用時調出即可。
【如何精簡】
這個問題是最重要的，因為，如果不精簡，在枚舉狀態以及轉移的時候就會枚舉到很多不合法狀態，導致時間浪費。
所謂精簡，是指在預處理以及DP過程中，盡量避開不合法狀態。
（1）預處理中的精簡：
包括3個部分：
<1>找到所有可能的合法狀態并編號：根據題意限制，有的狀態在階段內就不合法（比如本題，一行一階段，那么凡是有兩個1位的距離小于2的狀態都不合法），而且這種狀態所占的比重往往還很大（本題中，M=10時，也只有60種可能的合法狀態），此時，為了找到這些合法狀態，可以DFS構造實現。
需要注意的是，有的題不光要找到一個階段內的合法狀態，還要找到兩個或兩個以上階段內的合法狀態（比如那個有關多米諾骨牌的題），此時需要兩個int同時DFS；
在找到合法狀態以后，需要對每個合法狀態進行編號，以達到“壓縮”的目的。這里就涉及到了狀態編號和狀態表示的問題：比如，狀態1001，表示為9，在DFS中第一個被搜到，因此編號為0，不要搞混了這兩個（尤其不要搞混“編號為0”和“狀態表示為0”，它們是不同的）。在預處理和DP的過程中，所有涉及到狀態的數組下標，全部是編號而不是表示，知道編號要求表示，可以在DFS中記錄的數組里面調，而知道表示要求編號，可以利用逆數組或者哈希；
<2>找到每一階段的合法狀態：即使是<1>中被判定為合法的狀態，在具體的各個階段中也未必合法（比如本題，如果某一行的某一個位置是'H'，不能放，而某一個狀態在這里放了，則不合法），因此要對每個階段再枚舉一遍，找到真正合法的狀態，并計入一個vector；
<3>找到狀態轉移中的合法狀態：在狀態轉移中，往往要求狀態不沖突（比如本題，在連續的三個階段中，都不能有某一位有兩個為1的情況），因此，還要枚舉每個狀態在轉移時與其不沖突的狀態，并計入vector。
注意，有時候這一步不是很容易進行，需要在DP過程中進行；
（2）DP過程中的精簡：
DP過程中，枚舉狀態、轉移決策都只枚舉合法的，在vector里面調（注意vector里記錄的全都是狀態編號而不是表示！），可以大大減少枚舉量，不過有時候，還會有一些時間浪費，這時候，可以采取一些其它的辦法來精簡，比如再次進行DFS構造合法狀態等。
總之，這類問題的目標就是“精簡，精簡，再精簡，使枚舉到的不合法狀態減到最少”。
代碼：
#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;
}