当前位置：首页 > news >正文

xmuoj [蒙德里安的梦想] 状压dp个人笔记

news 2025/7/1 17:12:55

本题是状压dp经典题目，很多人都是通过这一题开始对状压dp有所了解。

在进行讲解之前，我们先通过几个问答大致了解状压dp。

一、问答

1. 问题：什么是状压dp?

回答：状压dp即为状态压缩动态规划，何为状态压缩？怎么进行状态压缩？是个问题。

这个问题涉及到了状压dp的核心思想——把问题的状态压缩成整数，因为整数便于存储和进行状态转移。

2. 问题：状压dp状态的存储形式是？

回答：前面已经说了，问题的状态应该压缩成整数，但是单纯的10进制整数显然无法满足最小子问题的状态存储，或者说，浪费了很多存储空间。对于最小子问题，一般情况下，只有 1 和 0 两种状态，那么，我们用二进制存储显然更优。

3. 问题：用二进制存储状态只是存储上更优吗？

回答：不然，二进制天然的位运算可以大大加速状态转移。这也是状压dp不会超时的重要原因。

哈哈，关键词get到了吗？二进制、位运算 ✿✿ヽ(°▽°)ノ✿

二、下面进行例题讲解

错误思路我就不讲了，因为错误思路千奇百怪，我也是开始就想偏了（~~我上来就是dp[n][m]一顿转移~~）。

首先，我们应该明白的是，我们只能放横着放或者竖着放长方形，一旦横着放的确定了（横着的放法要在合理情况下，总不能让竖的放不了吧O(∩_∩)O ），那么竖着的一定就只有一种可能了，所以，我们只需考虑横着放有多少种合理的放法即可。

下面该怎么做呢？~~已经焦头烂额了，开始吟唱~~

对于第 i 列，我们假设 0~ i -1 列的横着放的长方形已经全部放好了，我们都知道，横着放的一定有突出的部分。

就比如说，对于这张图，第 i 列突出的部分是 0、1、3这三个位置，用二进制表示即为101100，对应十进制的44，所以，这个状态就是 f [ i ][ 44 ]

不难发现，第 i 列状态是由第 i-1 列的状态转移过来的

具体来说，f [ i ][ j ] +=所有满足条件的 f[ i-1][ k ]

要满足什么条件呢？

1. j 和 k不能重叠（显然长方形不能重叠放置，可以重叠的话放法就无穷尽了）

对于这个条件，保证 j&k==0 即可

2. j和k放完之后，第i-1列不能有连续奇数个0（因为这样就放不了竖着的了）

定义isok[ i ]表示 i 的二进制表示是否满足上述条件，isok[ i ] = true表示满足条件，

保证 isok[ j | k ]为 true 即可

三、C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
bool isok[M];
long long f[N][M];
int main() {while (cin >> n >> m, n || m) {for (int i = 0;i < 1<<n;i++) {//计算isok[i]isok[i] = true;int cnt = 0;for (int j = 0;j < n;j++) {if (i >> j & 1) {if (cnt % 2)isok[i] = false;cnt = 0;}else cnt++;}if (cnt % 2)isok[i] = false;}memset(f, 0, sizeof f);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 (isok[j | k] && !(j & k)) {//满足两个条件才能转移f[i][j] += f[i - 1][k];}}}}cout << f[m][0] << endl;//代表到 m列且没有突出的情况（列数为0~m-1,m列表示遍历完成了）}return 0;
}