总结 DP

发布日期: 2022-08-30

更新日期: 2022-10-15

文章字数: 2.1k

DP总结-状压dp

状压dp（状态压缩动态规划）是一种dp。（废话）

状压dp的核心就是把若干状态压缩为一个整数

通常要压缩的元素个数不超过 $15$ ，此时状态数共有 $2^{15}=32768$ 。

状压dp更多的是一种思想，常见于数位dp等需要记录大量信息的dp中。

集合的整数表示

注意，当集合元素个数较多的时候，可能需要使用 1ll<<n 或者 1ull<<n 。

基本表示：

空集：0

大小为 $n$ 的全集： (1 << n) - 1

第 $i$ 个元素 $x_i$ ：1 << i

交集：

$S\cap \{x_i\}$ ：(S >> i) & 1

$S\cap T$：S & T

并集：

$S \cup \{x_i\}$ ：S | (1 << i)

$S \cup T$ ：S | T

绝对补集：

$\sim!S$ ：U^S 或 U-S 或 (~S) & U ，U为全集

相对补集：

$S\setminus\{x_i\}$ ：S & (~(1 << i))

$S\setminus T$ ： S & (T^U)

集合的基数（元素个数）：

第一种不建议在使用C++20之前的版本使用。（~~但是可以偷懒~~）

int __builtin_popcount(unsigned int)
int __builtin_popcountll(unsigned long long)

// 虽然它参数是unsigned，但是可以直接传signed
    
int S = calc1();
cout << __builtin_popcount(S) << '\n';
long long T = calc2();
cout << __builtin_popcountll(T) << '\n';

第二种推荐使用

int popc(int x)
{
    int cnt=0;
    for(; x; x &= (x-1)) ++cnt; // 原理：每次去掉最后一位
    return cnt;
}

下面给出了一份代码，可以用来测试。

状压dp和一般的集合表示不太一样（~~毕竟是整数表示嘛~~）

例如 S=0010 表示的是 $S$ 只有第 $3$ 个元素

请注意代码均 #define int long long 了，下同。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

void print(int S,int n)
{
    for(int i=0; i<n; i++)
        ((S >> i) & 1) ? (cout << 1) : (cout << 0);
    cout << ' ';
}
int popc(int x)
{
    int cnt=0;
    for(; x; x &= (x-1)) ++cnt;
    return cnt;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    int n = 8, S = (1<<1) + (1<<3) + (1<<5);
    int U = (1 << n) - 1;
    int rS = S ^ U; // S 的绝对补集

    cout << "U = "; print(U,n); cout << '\n';
    cout << "|U| = " << n << '\n';

    cout << "---\n";

    cout << "S = "; print(S,n); cout << '\n';
    
    cout << "~S = "; print(rS,n); cout << '\n';

    cout << "---\n";
    
    int T = (1<<2) + (1<<5);
    cout << "|T| = " << __builtin_popcountll(T) << '\n';
    cout << "|T| = " << popc(T) << '\n';
    cout << "T = "; print(T,n); cout << '\n';

    cout << "---\n";

    cout << "S ∩ T = "; print(S&T,n); cout << '\n';
    cout << "S ∪ T = "; print(S|T,n); cout << '\n';
    
    return 0;
}

输出如下：

---
|T| = 2
|T| = 2
U = 11111111 
|U| = 8
---
S = 01010100 
~S = 10101011 
---
|T| = 2
|T| = 2
T = 00100100 
---
S ∩ T = 00000100 
S ∪ T = 01110100

集合的枚举

枚举 $n$ 个元素的所有子集

时间复杂度 $O(2^n)$

for(int i=0; i < (1 << n); i++) print(i,n);

如果要枚举非空子集就这么写

for(int i=1; i < (1 << n); i++) print(i,n);

如果要枚举非空真子集就这么写

for(int i=1; i < (1 << n) - 1; i++) print(i,n);

枚举 $S$ 所有的非空子集

时间复杂度 ${O(2^n)}$

for(int i=S; i; i = (i-1) & S) print(i,n);

如果要枚举非空真子集，只要这么写就行了

for(int i=S&(S-1); i; i = (i-1) & S) print(i,n);

枚举大小为 $n$ 的集合的所有非空子集的非空子集

时间复杂度 $\color{red}{O(3^n)}$ （证明在下面）

用到了上面那个东西

for(int u=0; u < (1 << n); u++) // 枚举大小为n的集合的子集
{
    print(u,n); cout << ": ";
    for(int i=u; i; i = (i-1) & u) print(i,n); // 枚举这个子集的子集
    cout << '\n';
}
/*
n=3的运行结果如下

000 : 
100 : 100 
010 : 010 
110 : 110 010 100 
001 : 001 
101 : 101 001 100 
011 : 011 001 010 
111 : 111 011 101 001 110 010 100 

*/

复杂度证明：

枚举大小为 $n$ 的集合 $S$ 的子集的复杂度
$O\left(\sum_{T\subseteq S}2^{|T|}\right)$
而 $S$ 中大小为 $k$ 的子集个数为 $\binom{n}{k}$ ，则枚举非空子集的复杂度为
$O\left(\sum_{i=1}^n\dbinom ni 2^i\right)$
根据二项式定理
$\sum_{i=1}^n\dbinom ni 2^i =\sum_{i=1}^n\dbinom ni 2^i1^{n-i} =(1+2)^n-1 =O(3^n) \qquad\square$

枚举 $n$ 个元素的所有大小为 $k$ 的子集

时间复杂度 $O(2^n)$

常数可能小一些，用处不是很大，而且不好记，目前没碰到过有用的地方。

int i = (1<<k)-1;
while(i < (1<<n))
{
    int x = i&(-i), y = i+x; print(i,n);
    i = ((( i & (~y) ) / x) >> 1) | y;
}

可能还有，待补。。咕咕咕。。。

同样的，示例代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

void print(int S,int n)
{
    for(int i=0; i<n; i++)
        ((S >> i) & 1) ? (cout << 1) : (cout << 0);
    cout << ' ';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n = 3,k;
    cout << "\n----\n"; cout << "all:\n";
    for(int i=0; i < (1<<n); i++) print(i,n); // all

    cout << "\n----\n"; cout << "no empty:\n";
    for(int i=1; i < (1<<n); i++) print(i,n); // no empty

    cout << "\n----\n"; cout << "no empty && no U:\n";
    for(int i=1; i < (1<<n)-1; i++) print(i,n); // no empty && no U
    cout << "\n----\n";

    n = 8;
    int S = (1<<0) + (1<<2) + (1<<5);
    cout << "S = "; print(S,n); cout << '\n';
    // subset (no empty)
    for(int i=S; i; i= (i-1) & S) print(i,n);

    cout << "\n----\n";

    // sub's sub in 3^n
    n = 3;
    for(int u=0; u < (1 << n); u++)
    {
        print(u,n); cout << ": ";
        for(int i=u; i; i = (i-1) & u) print(i,n);
        cout << '\n';
    }
    cout << "----\n";

    n = 3; k = 2;
    int i = (1<<k)-1;
    while(i < (1<<n))
    {
        int x = i&(-i), y = i+x; print(i,n);
        i = ((( i & (~y) ) / x) >> 1) | y;
    }
    cout << "\n----\n";
    return 0;
}

输出（加了个代码高亮便于区分…）


----
all:
000 100 010 110 001 101 011 111 
----
no empty:
100 010 110 001 101 011 111 
----
no empty && no U:
100 010 110 001 101 011 
----
S = 10100100 
10100100 00100100 10000100 00000100 10100000 00100000 10000000 
----
000 : 
100 : 100 
010 : 010 
110 : 110 010 100 
001 : 001 
101 : 101 001 100 
011 : 011 001 010 
111 : 111 011 101 001 110 010 100 
----
110 101 011 
----

斯坦纳树

详见斯坦纳树学习笔记

一种较为有趣的状压dp，涉及有关三角不等式的转移。

一些题目

直接在博客里搜状压dp就好了，这里是很久以前写的东西。

AT3913 XOR Tree

状态：压缩状态表示集合中 $1\sim15$ 是否出现（本题要求拆分出非空集）

转移方程：略

枚举集合，并枚举这个集合所有的真子集

for(int i=1; i<(1<<15); i++) // 所有可能的集合（要非空，不然无须dp，如果强行可能会挂）
{
    // do something ... （本题有个判断）
    for(int k=(i-1)&i; k; k=(k-1)&i) // 对于每个集合，枚举其所有「非空真子集」
        /*if(sxr[k]==0)*/ d[i]=min(d[i],d[k]+d[i^k]); 
    	// 这里的if是本题目需要的判断
    	// 后面的d[k]+d[i^k]就是将每个拆分成两个不同的非空子集的答案之和
}

这里枚举的是一个非可重集中1~15的存在情况（ $0$ 不影响异或和，所以不管）

而题目中需要知道这个集合的异或和，可以这样写

for(int i=1;i<(1<<15);i++) // 每个集合
    for(int j=0;j<15;j++)if((i>>j)&1)sxr[i]^=(j+1);
	// j+1就是原来这个数，第j位是状态

AT2657 [ARC078D] Mole and Abandoned Mine

详见 AT2657 [ARC078D] Mole and Abandoned Mine 题解

参考文献：

[1] 《挑战程序设计竞赛（第二版）》秋叶拓哉等

[2] 《离散数学（第六版）》屈婉玲等

[3] https://yhx-12243.github.io/OI-transit/records/ac2657%3Barc078F.html

[4] https://www.cnblogs.com/CDOI-24374/p/15876755.html

[5] https://oi-wiki.org/math/bit/

[6] https://shanlunjiajian.github.io/2021/04/04/state-dp/

q779

https://q779.cn/2022/08/30/dp-zong-jie-zhuang-ya-dp/

本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !

总结 DP

CF712E Memory and Casinos 题解

2022-08-30 OI

算法数学 DP 数据结构

AT2657 [ARC078D] Mole and Abandoned Mine 题解

2022-08-30 OI

算法图论 DP