有用二维的 dp A 掉的吗

OIerGuo @ 2023-11-01 23:43:23

by YCSluogu @ 2023-11-02 08:11:37

这玩意没法二维DP吧

by BVVD_FM @ 2023-11-02 08:37:58

应该没有吧，三维状压dp

by The_shy33 @ 2023-11-02 15:28:21

@OIerGuo 1,2,3,4行 跑第4行时，和第2，3行不能互相冲突， 但这样判断不能确保3和1没有冲突

by pV_equals_nRT @ 2023-11-07 22:18:39

滚动数组算吗？

#include <bits/stdc++.h>
using namespace std;

int n, m, f[100][10], v[100][1 << 10], c[1 << 10], s[10000], dp[2][1 << 10][1 << 10];
string str;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < m; j++) {
            f[i][j] = str[j] == 'P' ? 1 : 0;
        }
    }
    for (int i = 0; i < 1 << m; i++) {
        int _i = i;
        for (int j = 1; j <= m; j++) {
            c[i] += _i % 2;
            _i /= 2;
        }
    }
    bool p;
    int top = -1;
    for (int i = 0; i < 1 << m; i++) {
        p = 0;
        for (int j = 0; j < m - 2; j++) {
            if (i >> j & 1) {
                if (((i >> (j + 1)) & 1) || ((i >> (j + 2)) & 1)) {
                    p = 1;
                }
            }
        }
        for (int j = 2; j < m; j++) {
            if (i >> j & 1) {
                if (((i >> (j - 1)) & 1) || ((i >> (j - 2)) & 1)) {
                    p = 1;
                }
            }
        }
        if (!p) {
            s[++top] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= top; j++) {
            v[i][s[j]] = 1;
            for (int k = 0; k < m; k++) {
                if ((s[j] >> k & 1) && (!f[i][k])) {
                    v[i][s[j]] = 0;
                }
            }
        }
    }
    for (int j = 0; j < 1 << m; j++) {
        for (int k = 0; k < 1 << m; k++) {
            dp[0][j][k] = -114514;
            dp[1][j][k] = -114514;
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i <= top; i++) {
        dp[0][s[i]][0] = c[s[i]];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= top; j++) {
            for (int k = 0; k <= top; k++) {
                if (v[i][s[j]] && v[i - 1][s[k]] && (!(s[j] & s[k]))) {
                    int maxi = -1;
                    for (int l = 0; l <= top; l++) {
                        if (!(s[j] & s[l])) {
                            maxi = max(maxi, dp[0][s[k]][s[l]]);
                        }
                    }
                    dp[1][s[j]][s[k]] = maxi + c[s[j]];
                }
            }
        }
        for (int j = 0; j < 1 << m; j++) {
            for (int k = 0; k < 1 << m; k++) {
                dp[0][j][k] = dp[1][j][k];
                dp[1][j][k] = -114514;
            }
        }
    }
    int maxi = -1910810;
    for (int j = 0; j <= top; j++) {
        for (int k = 0; k <= top; k++) {
            if (v[n - 1][s[j]] && v[n - 2][s[k]]) {
                maxi = max(maxi, dp[0][s[j]][s[k]]);
            }
        }
    }
    printf("%d", maxi);
}