状压 dp
泛化
思想就是把一个表示“存在”的 “集合” 转换成一个二进制数 。
然后进行对应的转移。
具体细节
常见的一种状态是设 \(dp(msk)\) 表示达到 \(msk\) 这个状态所需的代价最值。
一种常见的的优化复杂度的方式就是把合法的状态（决策）全部处理出来存到一个辅助数组里面。
普通状压一般分两种，一种是基于联通性的状压DP（棋盘类），一种是集合类的状压DP。
前一种的典型就是“[POJ2411]莫德里安的梦想“，“[SCOI2005]互不侵犯”和“[NOI2001]炮兵阵地”。
这类问题一般都需要处理每一行的合法状态，然后进行转移，转移的阶段一般 都是 “行”。
后一种的典型就是“[NOIP2016]愤怒的小鸟”，“[NOIP2017]宝藏”
这类问题一般需要记录当前状态已经处理了哪些事件，转移的时候一般 以状态 \(msk\) 作为阶段，但是此时就要注意了，设计状态的时候一定要检查一下最优子结构和无后效性，因为只有 \(msk\) 的话很容易没法覆盖完状态空间！
这两种的共同点就是，某个变量的数据范围一般会很小 。
例题
要求你在 \(n \times m\) 的矩阵上放一些物品，有些位置不能放，你不能让两个物品挨着，求方案数并取模。
\(n,m \le 13\)
首先发现这一题的 \(n,m\) 都是 \(\le 13\) 的，所以我们考虑状压。
先考虑没有不能放的限制，我们用二进制预处理 出一行里所有的可行 状态 \(sta\) 。
这样子可以少枚举一层，不然会爆炸。
如果说我们处理出来的情况是我们处理到的那一行的原来的状态的子集，那么这个状态就是可行的。
意思就是说，比如你是这样子的：
原来的状态： 1 0 1 1 0 0 1 0 0 1 1 1
处理的状态： 1 0 1 0 0 0 1 0 0 1 0 1
也就是说，处理的状态当中放了草的位置在原来的地方都是可以种草的。那么就是可行的。
然后我们设 \(f_{i,j}\) 表示考虑第 \(i\) 行，你考虑处理出来的第 \(j\) 个状态的方案数。
如果说这第 \(j\) 个状态是可行的，那么这里就会有方案。
反之如果不可行，那么就不会转移到它，方案数是 \(0\) 。
考虑枚举上一行的所有可行状态 \(k\) ，然后方程就是 \(f_{i,j}=f_{i,j}+f_{i-1,k} , \text{if} \ sta(j)\& sta (k) =0\) 。
\(\ sta(j)\& sta (k) =0\) 是因为你需要判断上下有没有相邻的。
处理可行状态 \(sta\) 的话只需要枚举所有的 \(2^n\) 个状态，看他有没有两位是相邻的即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 #include <bits/stdc++.h> using namespace std ; const int si = 14 ; const int stasi = 4096 + 10 ; // 可行状态一定在 2n 范围以内.
const int bitsi = 4096 + 10 ; const int p = 100000000 ; inline int mod ( int x , int p ){ return x < 0 ? ( x + p ) - ((( x + p ) / p ) * p ) : x - (( x / p ) * p );} int n , m , cnt = 0 ; int f [ si ][ stasi ]; int sta [ stasi ], yard [ si ]; inline void init ( int n ){ for ( register int i = 0 ; i <= n ; ++ i ){ // 不要忘了都不放 (0) 也是可行的
if (( i & ( i << 1 )) != 0 || ( i & ( i >> 1 )) != 0 ) continue ; // 记得打括号
sta [ ++ cnt ] = i ; // 合法状态
// printf("%d\n",sta[cnt]);
} } inline bool valid ( int l , int s ){ if ( ! (( yard [ l ] & sta [ s ]) == sta [ s ])) return false ; // 状态符合第 l 行的情况
return true ; } int main (){ memset ( f , 0 , sizeof f ), scanf ( "%d%d" , & n , & m ); for ( register int i = 1 ; i <= n ; ++ i ){ for ( register int j = 1 , k ; j <= m ; ++ j ){ scanf ( "%1d" , & k ); if ( k ) yard [ i ] += ( 1 << ( m - j )); // 把每一行的状态转成一个二进制数
} // printf("%d\n",yard[i]);
} init (( 1 << m ) -1 ); // 去掉最后的的一个，不然会多一个状态。
for ( register int i = 1 ; i <= cnt ; ++ i ){ if ( valid ( 1 , i )) f [ 1 ][ i ] = mod ( 1 , p ); // 不要忘记这里也要判合法
} for ( register int i = 2 ; i <= n ; ++ i ){ for ( register int j = 1 ; j <= cnt ; ++ j ){ // 枚举当前层状态
if ( ! valid ( i , j )) continue ; // 状态是否符合当前行的情况
for ( register int k = 1 ; k <= cnt ; ++ k ){ // 枚举上一层状态
if (( sta [ j ] & sta [ k ]) != 0 ) continue ; // 上下不合法
f [ i ][ j ] = mod ( f [ i ][ j ] + f [ i -1 ][ k ], p ); } } } int res = 0 ; for ( register int i = 1 ; i <= cnt ; ++ i ){ res = mod ( res + f [ n ][ i ], p ); } return printf ( "%d \n " , mod ( res , p )), 0 ; }
给你一个 \(n\times m\) 的矩阵。
你可以用 \(1\times 2\) 的长方形去填充它，可以竖着也可以横着。
问恰好填满的方案数。
\(1\le n,m\le 11\) 。
仔细思考可以发现，如果当前只考虑第 \(i\) 行，那么无非就是三种情况：
用 \(1\times 2\) 的（==） 填充
用 \(2\times 1\) 的上一半填充。
用 \(2\times 1\) 的下半部分填充（并且上一行的对应位置是 \(2\times 1\) 的上一半）。
最麻烦的就是第二种情况。
所以考虑状压，设 \(msk\) 表示某一行的状态，第 \(i\) 位为 \(1\) 则表示对应的位置上放的是 \(2\times 1\) 的上一半。
所以，上一行的状态 \(msk_{i-1}\) 要想转移到当前行 \(msk_i\) ，必须满足 \(msk_{i-1} \operatorname{and} msk_i =0\) 。
但是也需要考虑第一种情况放不放的了。那么先把上一行的状态 \(\operatorname{or}\) 过来，那么下半部分的位置就确定了。
因为是 \(1\times 2\) 的，所以上下两个状态进行按位或之后，需要满足：任意 \(0\) 的连通块里，\(0\) 的个数是偶数个。
那么先预处理所有行内合法的状态。
然后枚举行，再枚举上一行的状态和当前行的状态进行转移即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 #include <bits/stdc++.h> using namespace std ; #define int long long
constexpr int si = 20 ; constexpr int stasi = 1 << 12 ; int n , m ; int f [ si ][ stasi ]; bool vis [ stasi ]; signed main (){ while ( scanf ( "%lld%lld" , & n , & m ) != EOF && n && m ){ for ( register int msk = 0 ; msk < ( 1 << m ); ++ msk ){ bool ff = false , cnt = false ; for ( register int i = 1 ; i <= m ; ++ i ){ if ( msk >> ( i -1 ) & 1 ) ff |= cnt , cnt = false ; else cnt ^= 1 ; } vis [ msk ] = ff | cnt ? 0 : 1 ; } memset ( f , 0 , sizeof f ), f [ 0 ][ 0 ] = 1 ; for ( register int i = 1 ; i <= n ; ++ i ){ for ( register int j = 0 ; j < ( 1 << m ); ++ j ){ for ( register int k = 0 ; k < ( 1 << m ); ++ k ){ if (( j & k ) != 0 || ! vis [ j | k ]) continue ; f [ i ][ j ] += f [ i -1 ][ k ]; } } } printf ( "%lld \n " , f [ n ][ 0 ]); } return 0 ; }
有 \(n\) 个二维平面上的点 \((x_i, y_i)\) 。
你需要选择 \(m\) 个二次函数 \(f(x) = ax^2+bx(a > 0)\) ，使得所有点被覆盖，且 \(m\) 最小。
\(1\le n \le 18, 1\le T \le 30\) 。
不妨设 \(dp(msk)\) 表示覆盖状态为 \(msk\) 时需要的最小操作次数。
众所周知三点才能确定一条抛物线，我们已知的只有 \((0, 0)\) .
所以转移枚举两个点，看一下过它们的二次函数能干掉哪些，转移就行。
有些点的位置比较特殊，由于 \(a > 0\) 所以可能存在一个点使得它无法和其它的构成二次函数。
此时我们是以 \(msk\) 为阶段，考察一下它的正确性，只会从 \(\text{popcnt}\) 小的转移到大的，每一层枚举的 \(n^2 + n\) 种可能一定可以覆盖完每一个阶段的状态，这是合法的。
这里是最优化问题，操作顺序是无关的，所以最优子结构也满足。
所以就枚举一下，复杂度 \(O(Tn^22^n)\) ，过不了。
然后考虑优化？首先如果枚举的 \(i, j\) 已经被覆盖了，就没必要转移了，证明显然。
然后我们刚才说了，顺序是不重要的，但是就是因为这样，我们会多算。
所以不妨钦定一个转移顺序，可以发现如果一个状态包含四个点两条线，\((1,3), (2,4)\) 。
那么我们先打 \((1, 3)\) 和先打 \((2, 4)\) 都没有区别。
那么不妨只考虑处理 \((1, 3)\) ，也就是只考虑过第一个点的转移。
因为阶段是 \(msk\) ，这样转移的话之前的也都已经算好了。
所以我们对于一个 \(msk\) 只需要考虑它最低位的 \(1\) 代表的点的转移就行了。
复杂度 \(O(Tn2^n)\) 。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 #include <bits/stdc++.h> using namespace std ; constexpr int si = 20 ; constexpr int stasi = 1 << 19 ; constexpr long double eps = 1e-8 ; int n , m ; struct Pig { long double x , y ; } a [ si ]; int f [ stasi ], att [ si ][ si ]; inline bool equal ( long double x , long double y ){ return fabs ( x - y ) < eps ; } int main (){ int T ; cin >> T ; while ( T -- ){ scanf ( "%d%d" , & n , & m ); for ( register int i = 1 ; i <= n ; ++ i ){ cin >> a [ i ]. x >> a [ i ]. y ; }
// if(n==1){ puts("1");continue; }
memset ( att , 0 , sizeof att ); for ( register int i = 1 ; i <= n ; ++ i ){ att [ i ][ i ] = 1 << ( i -1 ); for ( register int j = 1 ; j <= n ; ++ j ){ // if(i==j) continue; att[i][j]|=1<<(i-1),att[i][j]|=1<<(j-1);
long double x1 = a [ i ]. x , x2 = a [ j ]. x , y1 = a [ i ]. y , y2 = a [ j ]. y ; long double A = ( y1 / x1 - y2 / x2 ) / ( x1 - x2 ), B = ( y1 / x1 - A * x1 ); if ( A >= 0 ) continue ; for ( register int k = 1 ; k <= n ; ++ k ){ // if(k==i || k==j) continue;
if ( equal ( A * a [ k ]. x * a [ k ]. x + B * a [ k ]. x , a [ k ]. y )) att [ i ][ j ] |= 1 << ( k -1 ); } } } memset ( f , 0x3f , sizeof f ), f [ 0 ] = 0 ; for ( register int msk = 0 ; msk < ( 1 << n ); ++ msk ){ register int i = 0 ; for ( register int j = 1 ; j <= n ; ++ j ){ if ( ! ( msk >> ( j -1 ) & 1 )){ i = j ; break ; } } for ( register int j = 1 ; j <= n ; ++ j ){ f [ msk | att [ i ][ j ]] = min ( f [ msk | att [ i ][ j ]], f [ msk ] + 1 );
} } printf ( "%d \n " , f [( 1 << n ) -1 ]); } return 0 ; }
最后更新:
August 5, 2023