题目描述

注释版，仅记录。

时间复杂度

参考文献

C++ 代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N=10,M=1<<10;

int n,m;
int g[1010];
int f[2][M][M];
vector<int> state;
int cnt[M];

bool check(int state)
{
    for(int i=0;i<m;i++)
        if((state >> i &1) && ( (state >>i+1 &1) || (state>>i+2&1)))
        return false;
        //这只需要考虑前两行之间和和第i行的 &
        //不需要前两行之间再 & 一下了
    return true;
}

int count(int state)
{
    int res=0;
    for(int i=0;i<m;i++)
    {
        if(state>>i &1)
        {
            res++;
        }
    }
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            g[i]+=(c=='H') <<j;     //把字符串图形处理成二进制状态
        }
    }

    for(int i=0;i<1<<m;i++)
    {
        if(check(i))
        {
            state.push_back(i);
            cnt[i]=count(i);
        }
    }

    for(int i=1;i<=n;i++)
        for(int j=0;j<state.size();j++)
            for(int k=0;k<state.size();k++)
                for(int u=0;u<state.size();u++)
                {
                    int a=state[j],b=state[k],c=state[u];
                    if(a & b | a & c | b & c) continue;
                    if(g[i] & b | g[i-1] & a) continue;
                    f[i&1][j][k]=max(f[i&1][j][k],f[i - 1 & 1][u][j] + cnt[b]);
                }   //cnt[b]是b状态1的个数。
                    //&1 是为了 用滚动数组减少空间开销。

    int res=0;
    for(int i=0;i<state.size();i++)
    {
        for(int j=0;j<state.size();j++)
            res=max(res,f[n&1][i][j]);  //枚举出第n行每种状态对应第i-1行每种状态的最大值
    }

    cout<<res<<endl;

    return 0;
}