状压DP

引入：

Mondriaan’s Dream

要求使用 $1 \times 2$ 的矩形(可以旋转) 恰好将 $n \times m (1 \leq n, m \leq 11)$ 的矩形填满，求有多少种方式？

$o k_{i}$ 作为某一列的一种摆放的状态是否可摆，横着摆放且向下一列伸出 为 1，竖着摆放或由前一列伸出 为 0，
即： $\begin{matrix} 1 & 0 \end{matrix}$ $\begin{matrix} 0 \\ 0 \end{matrix}$

则对于 $i$ 列状态不可能会出现 0 个数为奇的情况。所以要将不可能的情况剔除掉( $o k_{i} = 0$ )。

只需要考虑横着的情况即可，即整个矩形的状态已经确定了，最终求 $f_{m, 0}$ 即可。

$f_{i, j}$ 表示列为 $i$ 时，状态为 $j$ 时的方案数。

转移方程：

f_{i, j} = \sum_{k = 0}^{2^{n} - 1} f_{i - 1, k} \times [valid]

分别枚举第 $i$ 列和 $i - 1$ 列，

$valid$ : 若第 $i$ 列和 $i - 1$ 列是不重叠的(也就是说， $i - 1$ 列是 1， $i$ 列一定为 0，一个 $(1, 0)$ 代表一个 $1 \times 2$ 的矩形的开始和结束)，即 $j & k = 0$ ，且放置后满足是可摆放的，即 $o k [j | k] = 1$

时间复杂度： $O (n \times 2^{2 n}) < 5 \times 10^{7}$

void solve() {
    vector<int> ok(1 << 15);
    vector<vector<int>> f(15, vector<int>(1 << 15));
    
    for (int i = 0;i < 1 << n;i++) {
        ok[i] = 1;
        int cnt = 0;
        for (int j = 0;j < n;j++) {
            if (i >> j & 1) {
                if (cnt & 1) {
                    ok[i] = 0;break;
                }
            } else {
                cnt++;
            }
        }
        if (cnt & 1)ok[i] = 0;
    }
    
    f[0][0] = 1;
    for (int i = 1;i <= m;i++) {
        for (int j = 0;j < 1 << n;j++) {
            for (int k = 0;k < 1 << n;k++) {
                if ((j & k) == 0 && ok[j | k]) {//两列状态兼容：不出现重叠的1，不出现连续的奇数个0 
                    f[i][j] += f[i - 1][k];
                }
            }
        }
    }
    cout << f[m][0] << '\n';
}

练习：

P1896 互不侵犯

在 $n \times n (1 \leq n \leq 9)$ 的棋盘里面放置 $k (0 \leq k \leq n^{2})$ 个国王，国王的攻击范围是围着一圈 8 个方向，要使得各个国王不互相攻击，一共有多少种摆放方案？

Solution：

设 $f_{i, j, s}$ 代表对于前 $i$ 行已经放置了 $s$ 个国王，且第 $i$ 行的状态是 $j$
则有：

f_{i, j, s} = \sum f_{i - 1, k, s - p o p c o u n t (j)} \times [valid]

$j, k$ 必须满足题目要求，判断第 $i, i - 1$ 行的可行性：

若 $j & k, (j ≪ 1) & k, j & (k ≪ 1)$ 满足任意一个，则不满足条件。否则满足条件。

对于每个状态都要保证是可行的

先预处理出所有可行的状态，再进行操作：

时间复杂度： $O (n^{3} \times 2^{2 n}) < 2 \times 10^{8}$ 值得注意的是：预处理了可行的状态后运算次数会显著降低

当 $n = 9$ 时，可行的状态也就 89 个，所以运算次数不超过 $n^{3} \times 89^{2} \leq 5774409$ ,运算量可以优化到极其小。

#define int long long
int f[11][1 << 11][11* 11];
void solve() {
    int n, king;cin >> n >> king;
    vector<int> ok;
    for (int i = 0;i < 1 << n;i++) {
        if ((((i << 1) | (i >> 1)) & i) == 0) {
            ok.push_back(i);
        }
    }
    f[0][0][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (auto j : ok) {
            for (auto k : ok) {
                if (j & k)continue;
                if ((j << 1) & k)continue;
                if (j & (k << 1))continue;
                for (int s = 0;s <= king;s++) {
                    int cnt = __builtin_popcount(j);
                    if (s - cnt >= 0) {
                        f[i][j][s] += f[i - 1][k][s - cnt];
                    }
                }
            }
        }
    }
    int ans = 0;
    for (auto x : ok)ans += f[n][x][king];
    cout << ans << '\n';
}

其他练习或遇到的题目：

date: 2024-06-12 22:17:12 时间过得真快。
计划：学习状压 DP，然后补掉 ARC 179，然后 VP CFdiv 4 ,然后补邀请赛，刷...

其他类型的 DP

SOS DP

SOS DP，全称 Sum over Subsets dynamic programming，意为子集和 DP，用来解决一些涉及子集和计算的问题。

「学习笔记」SOS DP - cyl06 - 博客园

高维前缀和总结(sosdp) - heyuhhh - 博客园

引入 ：

练习 ：

其他类型的 DP

SOS DP

引入：

练习：