$\LARGE\color{orange}{刷题日记(算法提高课)}$

这题说实话还挺秀的，值得多看几次

在状态表示上，由于第 $i$ 行的状态受到第 $i-1$ 行和第 $i-2$ 行的状态制约，因此我们表示状态的维度需要有两维，即

$f[i][j][k]$ 表示考虑前 $i$ 行，第 $i$ 行的状态为 $j$ ，第 $i-1$ 行的状态为 $k$ 的所有选法，其中 $j,\ k$ 均为二进制数

属性为所有选法当中 1 的个数的最大值

在地图的处理上与 AcWing 327. 玉米田 一模一样，P 设置为 0，H 设置为 1，并用 $g[i]$ 表示第 $i$ 行的二进制数

关键在于状态的枚举上

与之前相同，我们用 $heads$ 来存储可以相互转移的状态，与之前不同的是，之前的 $heads$ 存储的是 $states$ 当中的下标，这次直接存储二进制状态

那么对于第 $i$ 行的二进制状态 $j$，我们照常枚举 $states$ 即可，需要判断根 $g[i]$ 是否有冲突

对于第 $i-1$ 行的二进制状态 $p1$，我们从 $heads[j]$ 中枚举，这时的 $p1$ 与 $j$ 一定没有冲突

对于第 $i-2$ 行的二进制状态 $p2$，我们只能从 $heads[p1]$ 中枚举，此时的 $p2$ 可能会与 $j$ 产生冲突，因此需要做额外的判断

完整代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int f[2][M][M];

int g[N], cnt[M];
vector<int> states;
vector<int> heads[M];

int n, m;

bool check(int sta)
{
    return !(sta & sta >> 1 || sta & sta >> 2); 
}

int count(int sta)
{
    int ans = 0;
    while(sta)
        ans += sta & 1, sta >>= 1;
    return ans;
}

int main()
{
    cin >> n >> m;
    for(int i = 1, j = 0; i <= n; i++, j = 0)
        for(char c; j < m && cin >> c; j++)
            g[i] += (c == 'H') << j;

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

    for(int i = 0; i < states.size(); i++)
        for(int j = 0; j < states.size(); j++)
            if((states[i] & states[j]) == 0)
                heads[states[i]].push_back(states[j]);

    for(int i = 1; i <= n + 2; i++)
        for(int j : states)//枚举第i行的所有合法状态
            if((g[i] & j) == 0)//该状态是否与地图冲突
                for(int p1 : heads[j])//第i-1行所有能够转移到第i行的状态
                    for(int p2 : heads[p1])//第i-2行所有能够转移到第i-1行的状态
                        if((j & p2) == 0)//i-2行的状态是否与第i行的状态等价
                            f[i & 1][j][p1] = max(f[i & 1][j][p1], f[i - 1 & 1][p1][p2] + cnt[j]);
    cout << f[n + 2 & 1][0][0] << endl;
    return 0;
}