C++(g++ 7.5.0) 解法, 执行用时: 60ms, 内存消耗: 24316K, 提交时间: 2022-08-11 12:02:52

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[110][1<<10][1<<10];
int tot,z[1<<10];
int num[1<<10],ans;
int a[110];
char ch;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
	for(int j=1; j<=m; j++){
		cin>>ch;
		if(ch=='H')a[i]+=(1<<(j-1));
	}
	int nn=(1<<m)-1;
	for(int i=0; i<=nn; i++)
	if(!(i&(i<<1))&&!(i&i<<2)){
		tot++;
		z[tot]=i;
		int fl=i;
		while(fl>0)
		{
			if(fl&1)num[tot]++;
			fl>>=1;
		}
	}
	for(int i=1; i<=tot; i++)
	for(int j=1; j<=tot; j++)
	if(!(z[i]&z[j])&&!(z[i]&a[2])&&!(z[j]&a[1]))
    dp[2][i][j]=num[j]+num[i];
    for(int i=3;i<=n;i++)
    for(int j=1;j<=tot;j++)
    if(!(z[j]&a[i]))
    for(int k=1;k<=tot;k++)
    if(!(z[k]&a[i-1])&&!(z[k]&z[j]))
    for(int p=1;p<=tot;p++)
    if(!(z[p]&a[i-2])&&!(z[p]&z[k])&&!(z[p]&z[j]))
    {
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+num[j]);
        if(ans<dp[i][j][k])ans=dp[i][j][k];
    }
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 249ms, 内存消耗: 876K, 提交时间: 2021-09-30 01:21:09

#include<bits/stdc++.h>
using namespace std;
int N, M;

int main() {
  cin >> N >> M;
  vector<string> G(N);
  for (auto &s: G) cin >> s;
  int sz = 1; for (int i = 0; i < M; i++) sz *= 3;
  vector<int> cur(sz);
  cur[0] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0, bs = 1; j < M; j++, bs *= 3) {
      vector<int> nxt(sz);
      for (int s = 0; s < sz; s++) {
        int x = s / bs % 3;
        if (x == 0)  nxt[s] = max(cur[s], cur[s+bs]);
        else if (x == 1) nxt[s] = cur[s+bs];
        else if (x == 2 && G[i][j] == 'P') {
          if (j >= 1 &&  s/(bs/3)%3 == 2) continue;
          if (j >= 2 &&  s/(bs/9)%3 == 2) continue;
          nxt[s] = cur[s-bs-bs] + 1;
        }
      }
      cur = nxt;
    }
  }
  cout  << *max_element(cur.begin(), cur.end()) << endl;
}