一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
using namespace std;
const int N=110, M=(1<<10)+10, C=70, E=2;
 
int n, m;
int g[N];//山地平原情况
 
class DP
{
public:
    int f[E][C][C];//第几行，i-1状态，i状态
    int cnt[M];//状态的1的数量
    vector<int> correct, pre[C];//左右无相邻两格1的状态, 当前态能从哪个转移
 
public:
    DP()
    {
        initIO();
    }
 
    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }
 
    //返回x最后一位1
    int lowbit(int x)
    {
        return x&-x;
    }
 
    //得到x二进制含1的数量
    int get1Cnt(int x)
    {
        int sum=0;
        while(x) ++sum, x-=lowbit(x);
        return sum;
    }
 
    //检查x是否有相邻1, 有则true, 否则false
    bool checkL1(int x)
    {
        for(int i=0;i<m;i++)
            if((x>>i&1)&((x>>i+1&1)|(x>>i+2&1)))
                return true;
        return false;
    }
 
    //预处理
    void init()
    {
        fill(cnt, cnt+M, 0);
        fill(&f[0][0][0], &f[0][0][0]+E*C*C, 0);
 
        //预处理1数量和无相邻1合法态
        for(int i=0;i<(1<<m);++i)
            if (!checkL1(i))//若无邻1
            {
                cnt[i]=get1Cnt(i);
                correct.emplace_back(i);
            }
        //cout<<correct.size()<<endl;60最大
    }
 
    int work()
    {//像这里因为是求最大值，所以无需情况i层
        for(int i=1;i<=n;++i)//for(int i=1;i<=n;i++)枚举摆了几行
            for(int j=0;j<correct.size();++j)//枚举i-1状态
                for(int k=0;k<correct.size();++k)//枚举当前状态
                    for(int u=0;u<correct.size();++u)//枚举i-2行状态
                    {
                        int a=correct[k], b=correct[j], c=correct[u];
                        if((a&b)|(a&c)|(b&c)) continue;//检查纵向是否合法
                        if((g[i]&a)|(g[i-1]&b)) continue;//检查山地是否摆了, i-2状态在i-1时检查了，不合法无贡献
                        f[i&1][j][k]=max(f[i&1][j][k], f[i-1&1][u][j]+cnt[a]);
                    }
        int ans=0;
        for(int i=0;i<correct.size();++i)
            for(int j=0;j<correct.size();++j)
                ans=max(ans, f[n&1][i][j]);
        return ans;
    }
}dp;
 
int main()
{
    cin>>n>>m;
    dp.init();
    for(int i=1;i<=n;++i)
        for(int j=0;j<m;++j)
        {
            char ch;
            cin>>ch;
            g[i]+=(ch=='H')<<(m-j-1);//处理矩阵
        }
    cout<<dp.work();
}