企业官网建设流程全解析

P2704 [NOI2001] 炮兵阵地

思路

对于一行炮兵的分布，会产生影响的只有该行的地形以及前两行的炮兵分布。所以，我们可以使用状压DP，压缩前两行的分布讨论本行。

对于一行，我们可以预先处理出合法的分布，如果不做这一步，时间复杂度会过大。

正解

#include<bits/stdc++.h> using namespace std; const int N = 105; const int M = 15; int n, m; char ch[N][M]; int a[N]; int dp[N][1<<10][1<<10]; vector<int> mask[N]; inline bool check(int x) { vector<int> res; for(int i = m - 1; i >= 0; i--) { if(x >= (1 << i)) { res.push_back(m - i); x -= (1 << i); } } if(res.size() == 0) return true; for(int i = 0; i < res.size() - 1; i++) { if(res[i] + 2 >= res[i + 1]) return false; } return true; } int main() { cin>>n>>m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { cin>>ch[i][j]; a[i] <<= 1; if(ch[i][j] == 'H') a[i] += 1; } for(int i = 1; i <= n; i++) for(int S = 0; S < (1 << m); S++) if(!(S & a[i]) && check(S)) { mask[i].push_back(S); } if(n == 1) { int maxn = 0; for(int i : mask[1]) maxn = max(maxn, __builtin_popcount(i)); cout<<maxn; return 0; } for(int i : mask[2]) { for(int j : mask[1]) if(!(i & j)) { dp[2][i][j] = max(dp[2][i][j], __builtin_popcount(i) + __builtin_popcount(j)); } } for(int i = 3; i <= n; i++) { for(int S1 : mask[i]) { for(int S2 : mask[i - 1]) { if(S1 & S2) continue; for(int S3 : mask[i - 2]) { if((S1 & S3) || (S2 & S3)) continue; dp[i][S1][S2] = max(dp[i][S1][S2], dp[i-1][S2][S3] + __builtin_popcount(S1)); } } } } int ans = 0; for(int S1 : mask[n]) { for(int S2 : mask[n - 1]) { if((S2 & a[n - 1]) || !check(S2) || (S1 & S2)) continue; ans = max(ans, dp[n][S1][S2]); } } cout<<ans; return 0; }