题解 P2228 【[HNOI2001]洋洋吃蛋糕】

AC_Evil · 2020-10-15 15:31:41 · 题解

状压DP

尤其注意到m\leq 10，那必然想到状压来求解。

状压m位二进制表示当前行中在矩形内的点为1，其余为0。

转移到下一行必须要满足题目内矩形的合法条件。

而判断需要\mathcal O(m)的复杂度。

总复杂度为\mathcal O(nm\times 2^{2m})，看起来很容易TLE，考虑做些有用的优化。

比如感性理解来看很多转移都是无用的（大概有90\%），这样常数就变成1/10。

再然后判断发现可以通过位运算直接\mathcal O(1)。

这样复杂度可以变成\mathcal O(\frac1{10}\times n\times 2^{2m})

细节请君看代码（又短又快又简洁/se）

#include <bits/stdc++.h>

const int B = 10, L = 205;

int f[1<<B], g[1<<B], n, m, c[L][B];
std::vector<int> tran[1<<B];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &c[i][j]);
    for (int S = 0, U; S < 1<<m; S++)
        for (int T = 0; T < 1<<m; T++)
            if (U = S^T, !((U>>1|U<<1)&S&T)) tran[T].push_back(S);
    for (int i = 0; i < n; i++) {
        for (int S = 0; S < 1<<m; S++) {
            int sum = 0;
            for (int j = 0; j < m; j++) if (S&(1<<j)) sum += c[i][j];
            for (int j = 0; j < tran[S].size(); j++)
                g[S] = std::max(g[S], f[tran[S][j]] + sum);
        }
        memcpy(f, g, sizeof f); memset(g, 0, sizeof g);
    }
    int ans = 0;
    for (int S = 0; S < 1<<m; S++) ans = std::max(ans, f[S]);
    printf("%d", ans);
    return 0;
}