首先是考虑dp状态的问题：
这道题主要处理的是 上行和上上行的状态。
假如我们令dp[i][x]来表示状态，仅用dp[i-1][y]来转移是不够的
所以我们dp状态不仅要有本行的状态，还要用上一行的状态。
令dp[i][x][y]为第i行的状态为x，第i-1行的状态为y时，最多的炮兵个数
然后便是预处理。
要处理两个东西：第i行的合法状态，以及第i行状态合法时，第i-1行的合法状态
然后便是dp转移：
if( !(x&z) ) dp[i][x][y]=max(dp[i-1][y][z]+popcount(i)) (用滚动数组来优化空间复杂度，否则会MLE)
最后便是预处理出第一行的dp情况，即预处理出dp[1][x][0]的情况,以及第二行的dp情况
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second const int N=110; const int M=11; //const int inf=0x3f3f3f3f; //const ll INF=0x3ffffffffffff; int T,n,m,dp[5][1<<M][1<<M]; char s[N][M]; vector<int> v1[N]; vector<int> v2[N][1<<M]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) scanf("%s",s[i]); for(int i=1;i<=n;i++) { for(int j=0;j<(1<<m);j++) { if( (j&(j<<1)) || (j&(j<<2)) ) continue; bool f=1; for(int k=0;k<m;k++) if(s[i][k]=='H'&&(j&(1<<k))) f=0; if(f) v1[i].pb(j); } } int ans=0; for(int i=2;i<=n;i++) for(auto x:v1[i]) for(auto y:v1[i-1]) if(!(x&y)) v2[i][x].pb(y); for(auto x:v1[1]) v2[1][x].pb(0),dp[1][x][0]=__builtin_popcount(x),ans=max(ans,dp[1][x][0]); for(int i=2;i<=n;i++) for(auto x:v1[i]) for(auto y:v2[i][x]) for(auto z:v2[i-1][y]) if(!(x&z)) { dp[i%2][x][y]=max(dp[i%2][x][y],dp[(i-1)%2][y][z]+__builtin_popcount(x)); ans=max(ans,dp[i%2][x][y]); } printf("%d",ans); return 0; }