Luogu P2704 [NOI2001] 炮兵阵地

P2704 [NOI2001] 炮兵阵地思路对于一行炮兵的分布会产生影响的只有该行的地形以及前两行的炮兵分布。所以我们可以使用状压DP压缩前两行的分布讨论本行。对于一行我们可以预先处理出合法的分布如果不做这一步时间复杂度会过大。正解#includebits/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][110][110]; vectorint mask[N]; inline bool check(int x) { vectorint 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() { cinnm; for(int i 1; i n; i) for(int j 1; j m; j) { cinch[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)); coutmaxn; 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]); } } coutans; return 0; }