为啥要把i-1行放在dp循环最外面，然后再是第i和第i-2行，按理来说不应该第i行在最外面吗，这样的话可以保证枚举到第i行时第i-1行已被算过

同问

有一个地方没有看懂，枚举的时候分别枚举当前行，上一行，上上行三个状态，为什么在检查和w[]是否有冲突的时候上上行没有检查，而只检查当前行和上一行

有人问过，就搬过来了hh

这行实际上是检查当前行摆放是否合法。所以每行只需被检测一次即可。
检查g[i] & b时，g[i - 1] & a被上次循环，g[i - 2] : 0) & c被上上次循环检测过了。若非法相应的 f 必为0。

加多这个if(i >= 2 && (w[i - 2] & c) != 0) continue;也可以的

感谢解惑，我本来也是增加了 i >= 2 的判断，看了你的回答之后，我只保留了对当前行的检查 也是可以的

import java.util.*;
import java.io.*;
class Main {
    static int n, m;
    static boolean check(int u) {
        for (int i = 0; i < m; i++) {
            int i1 = ((u >> i) & 1);
            int i2 = ((u >> (i + 1)) & 1);
            int i3 = ((u >> (i + 2)) & 1);
            if (i1 + i2 + i3 > 1) {
                return false;
            }
        }
        return true;
    }
    static int count(int u) {
        int ans = 0;
        for (int i = 0; i < m; i++) {
            if (((u >> i) & 1) == 1) ans++;
        }
        return ans;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = r.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            s = r.readLine().split("");
            int num = 0;
            for (int j = 0; j < m; j++) {
                if (s[j].equals("H")) {
                    num += 1 << j;
                }
            }
            arr[i] = num;
        }

        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        // 预处理出合理的行
        for (int i = 0; i < 1 << m; i++) {
            if (check(i)) {
                list.add(i);
                map.put(i, count(i));
            }
        }
        int len = list.size();

        int ans = 0;
        int[][][] f = new int[2][len][len]; // f(i,j,k) 代表考虑前i行，第i-1行状态为j下标对应的值，第i行状态为k下标对应的值
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < len; j++) { // i
                for (int k = 0; k < len; k++) { // i - 1
                    for (int u = 0; u < len; u++) { // i - 2
                        int a = list.get(j), b = list.get(k), c = list.get(u);
                        if ((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
                        int a1 = arr[i], b1 = arr[i - 1];

                        // 理论上每一行都会被检查，所以只检查当前行就可以了，而无须检查第 i - 1 和 i - 2 行
                        if ((a & a1) != 0) continue; 
                        f[i & 1][k][j] = Math.max(f[i & 1][k][j], f[i - 1 & 1][u][k] + map.get(a));
                        ans = Math.max(ans, f[i & 1][k][j]);
                    }
                }
            }
        }
        w.write(ans + " ");

        w.flush();
        r.close();
        w.close();
    }
}

可是如果是非法的 f=0加上cnt[]后还是可能会更新当前值的吧

想请问一下为什么这个题和玉米田的题目都是只跟下标i-1的状态有关，但玉米田的那个题不能用滚动数组呢

也是可以用的，因为第i行只会用到第i-1行的数据

这是后面直接用值作为位置写的，和题解的有小小不同，原理是一样的

炮兵阵列：

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

using namespace std;

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

int n, m;
int f[2][M][M];
vector<int> state;
int w[N];
int cnt[M];

bool check(int s)
{
    for(int i = 0;i < m;i ++)
    {
        if((s >> i & 1) == 1 && ((s >> (i + 1) & 1) == 1 || (s >> (i + 2) & 1) == 1))
            return false;
    }
    return true;
}
int count(int s)
{
    int res = 0;
    for(int i = 0;i < m;i ++)
    {
        if((s >> i & 1) == 1) res ++;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        int t = 0;
        for(int j = 0;j < m;j ++)
        {
            char c;
            cin >> c;
            if(c == 'H') t += 1 << j;
        }
        w[i] = t;
    }

    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) != 0 || (a & c) != 0 || (b & c) != 0) continue;
                    if((w[i] & a) != 0 || (w[i - 1] & b) != 0) continue;
                    if(i >= 2 && (w[i - 2] & c) != 0) continue;
                    f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]);
                }
            }
        }
    }

    int res = 0;
    for(int j = 0;j < state.size();j ++)
        for(int k = 0;k < state.size();k ++)
        {
            int a = state[j], b = state[k];
            res = max(res, f[n & 1][a][b]);
        }

    cout << res << endl;

    return 0;

}

玉米田：

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

using namespace std;

const int N = 13, M = 1 << 12 , mod = 100000000;

int n, m;
int f[2][M];
int row[N];//记录每一行土地发育的状态
vector<int> state;//可行的状态
vector<int> head[M];//表示与M状态可以搭配的有什么状态

bool check(int s)
{
    for(int i = 0;i < m - 1;i ++)
    {
        if(((s >> i) & 1 == 1) && ((s >> (i + 1) & 1 == 1)))
            return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        int t = 0;
        for(int j = 0;j < m;j ++)
        {
            int x;
            cin >> x;
            if(x == 0) t += 1 << j;
        }
        row[i] = t;
    }
    for(int i = 0;i < 1 << m;i ++)
        if(check(i))
            state.push_back(i);

    for(int i = 0;i < state.size();i ++)
        for(int j = 0;j < state.size();j ++)
        {
            int a = state[i], b = state[j];
            if((a & b) == 0) 
            {
                head[a].push_back(b);
            }
        }
    f[0][0] = 1;
    for(int i = 1;i <= n + 1;i ++)
    {

        for(int a = 0;a < state.size();a ++)
        {
            f[i & 1][state[a]] = 0;//这个必须加
            if((row[i] & state[a]) == 0)
            {
                for(int b = 0;b < head[state[a]].size();b ++)
                {
                    f[i & 1][state[a]] = (f[i & 1][state[a]] + f[i - 1 & 1][head[state[a]][b]]) % mod;
                }
            }
        }
    }
    long long res = 0;
    for(int i = 0;i < 1 << m;i ++) res = (res + f[n & 1][i]) % mod;

    cout << res << endl;


    return 0;
}

谢谢大佬，我明白了，玉米田这道题在开始新的行的时候必须得把当前行的值都清空，不然会受到上一行的影响，也就是f[i & 1][state[a]] = 0;必须得有。

是的

f[i & 1][j][k] = Math.max(f[i & 1][j][k], f[i - 1 & 1][k][u] + cnt[a]);
这个地方，会不会存在可能，f[i & 1][j][k]存储的上一次最大值比现在所有的f[i - 1 & 1][k][u] + cnt[a]都要大，举个例子，i=5的时候，记录了一个f[5 & 1][j][k]，到i=7的时候，会不会所有的f[6 & 1][k][u] + cnt[a]都比f[5 & 1][j][k]小，这样第七行存储的值其实是第五行的状态呀

会，第5层的集合的最大值会给第6层，第6层集合的最大值会给第7层