【題意】：司令部的將軍們打算在N*M的網(wǎng)格地圖上部署他們的炮兵部隊。一個N*M的地圖由N行M列組成，地圖的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）；一支炮兵部隊在地圖上的攻擊范圍如圖中黑色區(qū)域所示： 

如果在地圖中的灰色所標(biāo)識的平原上部署一支炮兵部隊，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網(wǎng)格均攻擊不到。從圖上可見炮兵的攻擊范圍不受地形的影響。 
現(xiàn)在，將軍們規(guī)劃如何部署炮兵部隊，在防止誤傷的前提下（保證任何兩支炮兵部隊之間不能互相攻擊，即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊范圍內(nèi)），在整個地圖區(qū)域內(nèi)最多能夠擺放多少我軍的炮兵部隊。  

【題解】：經(jīng)典的狀態(tài)壓縮dp。
              因為每行最多只有10個格子，考慮使用狀態(tài)壓縮。
              無效的狀態(tài)有很多，需要先預(yù)處理出所有合法狀態(tài)，最多只有60種，存放在st[]。
              設(shè)dp[i][j][k]表示當(dāng)前第i行的狀態(tài)為st[j]且第i-1行的狀態(tài)為st[k]能夠擺放部隊的最大值。

              轉(zhuǎn)移方程：
                     dp[i][j][k] = max(cnt[j] + dp[i-1][k][kk])

              最后的ans = max(dp[n-1][i][j]).

【代碼】：
  1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 #include "set"
 13 #include "utility"
 14 using namespace std;
 15 typedef pair<int, int> pii;
 16 #define pb push_back
 17 #define mp make_pair
 18 #define fi first
 19 #define se second
 20 #define sof(x) sizeof(x)
 21 #define lc(x) (x << 1)
 22 #define rc(x) (x << 1 | 1)
 23 #define lowbit(x) (x & (-x))
 24 #define ll long long
 25 const int inf = 1 << 25;
 26 int n, m;
 27 char maz[110][15];
 28 int row[110];
 29 int dp[110][70][70];
 30 int st[70], tot, cnt[70];
 31 
 32 void init() {
 33     tot = 0;
 34     memset(cnt, 0, sof(cnt));
 35     int nn = 1 << m;
 36     for(int i = 0; i < nn; i++) {
 37         bool flag = true;
 38         int tmp = 0;
 39         for(int j = m - 1; j >= 0; j--) {
 40             if(i & (1 << j)) {
 41                 tmp++;
 42                 if((j >= 1) && (i & (1 << (j-1)))) {
 43                     flag = false;
 44                     break;
 45                 }
 46                 if((j >= 2) && (i & (1 << (j-2)))) {
 47                     flag = false;
 48                     break;
 49                 }
 50             }
 51         }
 52         if(flag) {
 53             st[tot] = i, cnt[tot++] = tmp;
 54         }
 55     } 
 56 }
 57 
 58 void solve() {
 59     init();
 60     for(int i = 0; i < n; i++)
 61         for(int j = 0; j < tot; j++)
 62             for(int k = 0; k < tot; k++)
 63                 dp[i][j][k] = -inf;
 64 
 65     for(int i = 0; i < tot; i++) {
 66         if(!(st[i] & row[0])) dp[0][i][0] = cnt[i];
 67         else dp[0][i][0] = -inf;
 68         for(int j = 1; j < tot; j++) dp[0][i][j] = -inf;
 69     }
 70 
 71     for(int i = 1; i < n; i++)
 72         for(int j = 0; j < tot; j++)
 73             if(!(row[i] & st[j])) 
 74                 for(int k = 0; k < tot; k++)
 75                     if(!(st[j] & st[k]))
 76                         for(int kk = 0; kk < tot; kk++)
 77                             if(!(st[j] & st[kk]))
 78                                 dp[i][j][k] = max(dp[i][j][k], cnt[j] + dp[i-1][k][kk]);
 79 
 80     int ans = 0;
 81     for(int i = 0; i < tot; i++)
 82         for(int j = 0; j < tot; j++)
 83             ans = max(ans, dp[n-1][i][j]);
 84     printf("%d\n", ans);
 85 }
 86 
 87 int main() {
 88     while(~scanf("%d%d", &n, &m)) {
 89         memset(row, 0, sof(row));
 90         for(int i = 0; i < n; i++) {
 91             scanf("%s", maz[i]);
 92             for(int j = m - 1; j >= 0; j--) {
 93                 row[i] <<= 1;
 94                 if(maz[i][j] == 'H') row[i] |= 1;
 95             }
 96         }
 97         solve();
 98     }
 99     return 0;
100 }
101