上一题的升级版
dp[i][j][k] 表示第 i 行状态为 k 第i-1行状态为 j
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 2005
#define INF 0x3f3f3f3f
#define inf 10000000
#define MOD 100000000
#define ULL unsigned long long
#define LL long long using namespace std; char g[110][15];
int dp[105][70][70], mapp[110], sta[70], cc[70];
int n, m, num; bool if_ok(int x) {
if(x & (x<<1)) return false;
if(x & (x<<2)) return false;
return true;
} int countone(int x) {
int ans = 0;
while(x) {
++ ans;
x = x&(x-1);
}
return ans;
} void init() {
memset(dp, -1, sizeof(dp));
memset(mapp, 0, sizeof(mapp));
num = 0;
for(int i = 0; i < (1<<m); ++ i) {
if(if_ok(i)) sta[num++] = i;
}
// printf("num : %d\n", num);
} int main()
{
while(scanf("%d%d", &n, &m) == 2) {
init();
// printf("ff: %d\n", num);
for(int i = 0; i < n; ++ i) {
scanf("%s", g[i]);
}
for(int i = 0; i < n; ++ i) {
for(int j = 0; j < m; ++ j) {
if(g[i][j] == 'H') mapp[i] = mapp[i] | (1<<j);
}
}
for(int i = 0; i < num; ++ i) {
cc[i] = countone(sta[i]);
if((mapp[0] & sta[i]) == 0) {
dp[0][0][i] = cc[i];
}
}
for(int i = 0; i < num; ++ i) {
if(mapp[1] & sta[i]) continue;
for(int j = 0; j < num; ++ j) {
if(sta[j]&sta[i]) continue;
if(dp[0][0][j] == -1) continue;
dp[1][j][i] = max(dp[1][j][i], dp[0][0][j]+cc[i]);
}
}
for(int i = 2; i < n; ++ i) {
for(int j = 0; j < num; ++ j) {
if(mapp[i] & sta[j]) continue;
for(int k = 0; k < num; ++ k) {
if(sta[k] & sta[j]) continue;
for(int q = 0; q < num; ++ q) {
if(sta[q] & sta[k] || sta[q] & sta[j]) continue;
if(dp[i-1][k][q] == -1) continue;
dp[i][q][j] = max(dp[i][q][j], dp[i-1][k][q]+cc[j]);
}
}
}
}
int ans = 0;
for(int i = 0; i < n; ++ i) {
for(int j = 0; j < num; ++ j) {
for(int k = 0; k < num; ++ k) {
ans = max(ans, dp[i][j][k]);
}
}
}
printf("%d\n", ans);
}
return 0;
}