超了好久都不对……（悲

修改了好几次的代码

#include <iostream>
using namespace std;
int f[(1<<10)][(1<<10)][3], sum[(1<<10)];
bool a[105];

inline int getsum(int S){
	int tot = 0;
	while (S) {
		tot += (S & 1);
		S >>= 1;
	}
	return tot;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) {
			char x;
			cin >> x;
			a[i] <<= 1; a[i] += (x == 'H'?1:0);
		}
	for (int i = 0; i < (1 << m); i++) {
		sum[i] = getsum(i);
		if (!(i & a[0] || (i & (i << 1)) || (i & (i << 2)))) f[0][i][0] = sum[i];
	}
	for (int i = 0; i < (1 << m); i++) { //第一行状态
		for (int j = 0; j < (1 << m); j++) { //第二行状态
			if (!(i & j || i & a[0] || j & a[1] || (i & (i << 1)) || (i & (i << 2)) || (j & (j << 1)) || (j & (j << 2)))) 
				f[i][j][1] = sum[i] + sum[j];
		}
	}
	for (int i = 2; i < n; i++)
		for (int L = 0; L < (1 << m); L++) {
			if (L & a[i - 1] || (L & (L << 1)) || (L & (L << 2))) continue;
			for (int S = 0; S < (1 << m); S++) {
				if (S & a[i] || L & S || (S & (S << 1)) || (S & (S << 2))) continue;
				for (int LS = 0; LS < (1 << m); LS++) {
					if (LS & L || LS & S || LS & a[i - 2] || (LS & (LS << 1)) || (LS & (LS << 2))) continue;
					f[L][S][i % 3] = max(f[L][S][i % 3], f[LS][L][(i - 1) % 3] + sum[S]);
				}
			}
		}
	int ans = 0, k = (n-1) % 3;
	for (int i = 0; i < (1 << m); i++)
		for (int j = 0; j < (1 << m); j++) 
			ans = max(ans, f[i][j][k]);
	cout << ans;
}

题解代码链接

#include<iostream>
using namespace std;
int n,m,ans,dp[(1<<10)][(1<<10)][3]/*滚动数组*/,a[105],Sum[(1<<10)];
char x;
int getsum(int S)	//当前状态 S 里面包含几个 1
{
	int tot=0;
	while(S) {if(S&1) tot++; S>>=1;}
	return tot;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>x,a[i]<<=1,a[i]+=(x=='H'?1:0);	//转成二进制数
	for(int i=0;i<(1<<m);i++)
		Sum[i]=getsum(i);	//初始化 Sum 数组
	for(int S=0;S<(1<<m);S++)
		if(!(S&a[0] || (S&(S<<1)) || (S&(S<<2))))
			dp[0][S][0]=Sum[S];	//初始化
	for(int L=0;L<(1<<m);L++)
		for(int S=0;S<(1<<m);S++)
			if(!(L&S || L&a[0] || S&a[1] || (L&(L<<1)) || (L&(L<<2)) || (S&(S<<1)) || (S&(S<<2))))	//谜之一长串特判
				dp[L][S][1]=Sum[S]+Sum[L];
	for(int i=2;i<n;i++)
		for(int L=0;L<(1<<m);L++)
		{
			if(L&a[i-1] || (L&(L<<1)) || (L&(L<<2))) continue;	//特判
			for(int S=0;S<(1<<m);S++)
			{
				if(S&a[i] || L&S || (S&(S<<1)) || (S&(S<<2))) continue;
				for(int FL=0;FL<(1<<m);FL++)
				{
					if(FL&L || FL&S || FL&a[i-2] || (FL&(FL<<1)) || (FL&(FL<<2)))	continue;
					dp[L][S][i%3]=max(dp[L][S][i%3],dp[FL][L][(i-1)%3]+Sum[S]);		//滚动数组的实现方法
				}
			}
		}
	for(int L=0;L<(1<<m);L++)
		for(int S=0;S<(1<<m);S++)
			ans=max(ans,dp[L][S][(n-1)%3]);	//结束状态可以是最后一行的任何状态
	cout<<ans;
	return 0;
}