看到 m <= 10，就知道这道题可定是状压dp。
还是一行一行dp，可见当前第 i 行能否放炮兵，除了和第 i 行的地形有关，还和 i - 1, i - 2行炮兵的放置状态有关。
因此dp要开三维，dp[k][j][i] 表示第 i 行的放置状态为 j， i - 1 行的放置状态为h时最多能放几个炮兵。
那么如果k, j 都符合条件的话, dp[k][j][i] = max(dp[k][j][i], dp[h][k][i - 1], sum[j]).
其中 h 表示i - 2行的放置状态，sum[j] 表示当前的放置状态有多少个炮兵，比如 j 状态是100100,那么sum[j] = 2。
然后我们枚举行数 i ，再枚举 i 行的状态 j，如果和地形shape[i]不冲突的话，再枚举 i - 1的状态 k，如果和shape[i - 1]以及 j 不冲突就再枚举 i - 2 的状态，再判断，然后更新dp。
理论上这样dp就行了，然而因为每一种状态都有210，210 * 210 * 100 = 1e8，空间开不下，而且时间复杂度为O(23m * n)卡在TLE的边缘，所以要优化一下。
我们可以预处理所有合法的放置状态，即同一行每两个炮兵之间的距离大于等于2，比如100001，而10100就不合法。这么做呢，还是O(2m)枚举状态i，然后如果 i 左移一位、两位和右移一位、两位和 i 位与起来都是0，就说明状态符合了。（当然也可以逐位判断，O(m * 2m)）。
不过dp[1]和dp[2]要单独处理，因为dp[1]只受shape[1]制约，dp[2]只受上一行状态和shape[2]制约。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 105; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 26 if(last == '-') ans = -ans; 27 return ans; 28 } 29 inline void write(ll x) 30 { 31 if(x < 0) x = -x, putchar('-'); 32 if(x >= 10) write(x / 10); 33 putchar(x % 10 + '0'); 34 } 35 36 int n, m; 37 char c[maxn]; 38 int shap[maxn], sum[maxn], s[maxn], cnt = 0; 39 int dp[maxn][maxn][maxn]; 40 41 int getsum(int x) 42 { 43 int ret = 0; 44 for(; x; x >>= 1) ret += x & 1; 45 return ret; 46 } 47 void init1() 48 { 49 for(int i = 0; i < (1 << m); ++i) 50 if(!(i & (i << 1)) && !(i & (i << 2)) && !(i & (i >> 1)) && !(i & (i >> 2))) 51 { 52 s[++cnt] = i; 53 sum[cnt] = getsum(i); 54 if(!(shap[1] & i)) dp[0][cnt][1] = max(dp[0][cnt][1], sum[cnt]); 55 } 56 } 57 58 void init2() 59 { 60 for(int i = 1; i <= cnt; ++i) if(!(shap[2] & s[i])) 61 for(int j = 1; j <= cnt; ++j) if(!(shap[1] & s[j]) && !(s[i] & s[j])) 62 dp[j][i][2] = max(dp[j][i][2], dp[0][j][1] + sum[i]); 63 } 64 65 int main() 66 { 67 n = read(); m = read(); 68 for(int i = 1; i <= n; ++i) 69 { 70 scanf("%s", c + 1); 71 for(int j = 1; j <= m; ++j) if(c[j] == 'H') shap[i] |= (1 << (j - 1)); 72 } 73 init1(); init2(); 74 for(int i = 3; i <= n; ++i) 75 for(int j = 1; j <= cnt; ++j) if(!(shap[i] & s[j])) //当前行 76 for(int k = 1; k <= cnt; ++k) if(!(shap[i - 1] & s[k]) && !(s[j] & s[k])) //上一行 77 for(int h = 1; h <= cnt; ++h) if(!(shap[i - 2] & s[h]) && !(s[j] & s[h]) && !(s[k] & s[h])) //上上行 78 dp[k][j][i] = max(dp[k][j][i], dp[h][k][i - 1] + sum[j]); 79 int ans = 0; 80 for(int i = 1; i <= cnt; ++i) 81 for(int j = 1; j <= cnt; ++j) ans = max(ans, dp[i][j][n]); 82 write(ans); enter; 83 return 0; 84 }