【题意】中文题目，题意很简单！

【解题方法】

首先我们求的是最多能放多少个炮兵，那么假如我把所有的情况都枚举了，然后在得到的结果里面找一个最大值，那么是不是就可以了。其实这个题目的思想就是这么简单。

但是我们如果用一般的枚举的方法肯定会超时，那么就用到了状态压缩。因为这个题目中一个炮影响的是两行，所以我们要多定义一维的状态来表示当前行的上上一行的状态。 状态：dp【i】【j】【k】 第 i 行，状态为 k ，第 i-1 行状态为 j 的最大放的炮兵数目

转移方程 dp [ i ] [ j ] [ k ]  = max ( dp [ i ] [ j ] [ k ] , dp [ i - 1 ] [k ] [ l ] + num [ j ] )

【AC代码和详细解释】 

// //Created by just_sort 2016/12/21 //Copyright (c) 2016 just_sort.All Rights Reserved // //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/hash_policy.hpp> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> //isstringstream #include <iostream> #include <algorithm> using namespace std; //using namespace __gnu_pbds; typedef long long LL; //typedef pair<int, LL> pp; #define REP(i, n) for(int i = 0; i < n; i++) #define REPZ(i, n) for(int i = 1; i <= n; i++) #define MP(x,y) make_pair(x,y) const int maxn = 1100; const int maxm = 1<<12; const int inf = 0x3f3f3f3f; //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head int n, m, num[110], top; //记录每一行拥有的炮兵的个数 int st[70], cur[110];//每一行的转态和输入的地的状态 int dp[110][70][70]; //dp[i][j][k]在第i行状态为j，在第i-1行状态为k的最大方案数 bool judge1(int x)//判断二进制相邻的1或者间隔2个位置,即是炮兵横着不能攻击到 { if(x&(x<<1) || x&(x<<2)) return false; else return true; } bool judge2(int i, int k)//判断当前行和上一行的状态是否出现冲突 { return cur[i] & st[k]; } void init1() //关键数组初始化 { memset(num, 0, sizeof(num)); memset(st, 0, sizeof(st)); memset(cur, 0, sizeof(cur)); memset(dp, 0, sizeof(dp)); top = 0; } void init2() //对不必要的状态进行剔除 { int total = 1 << m; for(int i = 0; i < total; i++) { if(judge1(i)) st[++top] = i; } } //int cal(int x) //计算状态x里面1的个数 //{ // int cnt = 0; // while(x) // { // if(x&1) cnt++; // x >>= 1; // } // return cnt; //} int main() { while(scanf("%d%d", &n, &m)!=EOF) { init1(); init2(); char x; int ans = 0; for(int i = 1; i <= n; i++) //输入的地的状态 { getchar(); for(int j = 1; j <= m; j++) { scanf("%c", &x); if(x =='H') cur[i] += (1 << (j-1)); } } //初始化DP装态 for(int i=1; i<=top; i++) { num[i] = __builtin_popcount(st[i]); if(!judge2(1, i)) { dp[1][i][1] = num[i]; //第1行状态为i,第0行状态为 ans = max(ans, num[i]); //更新一下当前最大值 } } //状态转移 for(int i = 2; i <= n; i++) //枚举行 { for(int j = 1; j <= top; j++)//当前行状态 { if(judge2(i, j)) continue; for(int l = 1; l <= top; l++) //上上行状态 { if(st[j] & st[l]) continue; for(int k = 1; k <= top; k++){ //上一行状态 if(st[j] & st[k]) continue; dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] + num[j]); //状态转移 ans = max(ans, dp[i][j][k]); //更新答案 } } } } //输出答案 printf("%d\n", ans); } return 0; }