mydcwfy's Blog

状态压缩 DP

Posted on
Symbols count in article: 5.9k Reading time ≈ 13 mins.

分为两种：基于连通性的 DP（棋盘式）和集合式（表示一个元素是否在集合内）。

状态压缩 DP

2. 例题

T1：蒙德里安的梦想

题目传送门 AcWing

T2：最短 Hamilton 路径

题目传送门 AcWing

上面两个题都比较简单，这里不再做详细的讲解。

T3：骑士

题目传送门 LOJ

观察到，第 $i$ 行的放置情况和 $i-1$ 相关。

所以，我们可以考虑将第 $i-1$ 行的情况存储下来，对于每一个 $i-1$ 的情况，都剋容易地求出 $i$ 行的情况，就可以转移了。

首先考虑，怎样存储当前行的状态。

观察到 $n$ 很小，于是我们可以将 $n$ 个 01 按位压缩为一个二进制数。

具体地，如果 $j$ 位为 1，则第 $j$ 个摆放了国王。

回到本题，还要考虑放了几个国王，于是还要存储，可以表示为 $f[i,j,sta]$ 表示处理到第 $i$ 行，摆放了 $j$ 个国王，且第 $i$ 行状态为 $sta$ 的总种类数。

再考虑转移，我们首先要保证当前行本身是合法的。

其次，我们要保证 $i$ 行与 $i-1$ 行是合法的。

时间复杂度为 $O(2^n\times n\times k)$，实际远远达不到。

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
50
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=12,K=N*N,S=(1<<N);
long long f[N][K][S];
bool st[S];
int num[S];

bool check(int s)
{
    for (int bit=0;bit<12;++bit)
        if ((s>>bit&1)&(s>>bit+1&1)) return false;
    return true;
}

int main()
{
    int n,k;scanf("%d %d",&n,&k);
    for (int s=0;s<(1<<n)-1;++s)
    {
        st[s]=check(s);
        if (st[s])
        {
            int tmp=s;
            while (tmp)
            {
                num[s]++;
                tmp-=(tmp&-tmp);
            }
        }
    }
    f[0][0][0]=1;
    for (int i=1;i<=n;++i)
        for (int s=0;s<(1<<n)-1;++s)
        {
            if (!st[s]) continue;
            for (int ls=0;ls<(1<<n)-1;++ls)
                if (st[ls]&&!(s&(ls<<1))&&!(s&ls)&&!((s<<1)&ls))
                {
                    for (int j=num[s];j<=k;++j) f[i][j][s]+=f[i-1][j-num[s]][ls];
                }
        }
    long long res=0;
    for (int s=0;s<(1<<n)-1;++s) res+=f[n][k][s];
    printf("%lld\n",res);
    return 0;
}

T4：玉米田

题目传送门 AcWing

是上一题的变式与扩展。其实差不多。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include"algorithm"
using namespace std;

typedef long long ll;
const int N=14,S=(1<<N);
const ll Mod=1e8;
ll f[N][S];
int n,m;
bool a[N][N];

bool valid(int l,int s)
{
    for (int i=1;i<=m;++i)
        if ((!a[l][i])&(s>>i-1&1)) return false;
    for (int i=0;i<m-1;++i)
        if ((s>>i&1)&(s>>i+1&1)) return false;
    return true;
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
    f[0][0]=1;
    for (int i=1;i<=n;++i)
        for (int s=0;s<(1<<m);++s)
        {
            if (!valid(i,s)) continue;
            for (int ls=0;ls<(1<<m);++ls)
                if (valid(i-1,ls)&&!(s&ls))
                    f[i][s]+=f[i-1][ls];
        }
    ll res=0;
    for (int s=0;s<(1<<m);++s) res=(res+f[n][s])%Mod;
    cout<<res<<endl;
    return 0;
}

T5：[NOI2001]炮兵阵地

题目传送门 Luogu

题目传送门 AcWing

本题和上面的题比较类似，但是还是有一些区别：

  1. 射程变为了 2 格。
  2. 是求最大放置数。

一个很明显的想法就是维护上面 2 行的信息。

使用 $f[i,j,k]$ 表示处理到第 $i$ 行，且第 $i$ 行状态是 $j$，第 $i-1$ 行的状态是 $k$。

状态之间转移时，我们可以根据第 $i-2$ 行来计算。

又有了第 $i-1$ 行的状态，我们就可以计算了。

但是，时间复杂度为 $O(2^{3m}\times n)$，已经超出了时间限制。

于是，我们可以先将合法的情况先存下来，再进行计算。

另外，空间 $O(2^{2m}\times n)$，可能超过空间限制，我们使用滚动数组。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=101,S=1<<10;
vector<int> st;
int f[2][S][S];
int v[N],n,m;
int cnt[S];

bool valid(int s)
{
    for (int i=0;i<m;++i)
        if ((s>>i&1)+(s>>i+1&1)+(s>>i+2&1)>=2) return false;
    return true;
}

int num(int s)
{
    int res=0;
    while (s)
    {
        res++;
        s-=(s&-s);
    }
    return res;
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i)
    {
        char op[14];
        scanf("%s",op);
        for (int j=0;j<m;++j) v[i]|=(op[j]!='P')<<j;
    }
    for (int s=0;s<(1<<m);++s)
        if (valid(s))
        {
            st.push_back(s);
            cnt[st.size()-1]=num(s);
        }
    for (int i=1;i<=n;++i)
        for (int i0=0;i0<st.size();++i0)
            for (int i1=0;i1<st.size();++i1)
            {
                int &s0=st[i0],&s1=st[i1];
                if ((s0&v[i])|(s1&v[i-1])|(s0&s1)) continue;
                for (int i2=0;i2<st.size();++i2)
                {
                    int &s2=st[i2];
                    if ((s2&v[i-2])|(s0&s2)|(s1&s2)) continue;
                    f[i&1][i0][i1]=max(f[i-1&1][i1][i2]+cnt[i0],f[i&1][i0][i1]);
                }
            }
    int res=0;
    for (int i=0;i<st.size();++i)
        for (int j=0;j<st.size();++j)
            res=max(res,f[n&1][i][j]);
    cout<<res<<endl;
    return 0;
}

T6：[NOIP2016]愤怒的小鸟

题目传送门 Luogu

题目传送门 AcWing

前面讲的都是棋盘型的状态压缩 DP，现在我们开始讲集合型。

首先，函数为 $y=ax^2+bx(a<0,b>0)$ 只要确定了两个点，就可以求出抛物线。

观察到 $n\leq18$，所以我们可以首先将 $\dfrac{n(n-1)}{2}$ 个抛物线以及经过的点预处理出来。

然后，本题就转化为了重复覆盖问题。

可以使用 Dancing Links 求解，也可以使用状态压缩 DP 求解。

我的 Dancing Links Blog

这里讲一下状态压缩 DP。

首先，我们考虑 DFS.

在此基础上，我们将其改为一个记忆化搜索，用一个二进制数来表示各个元素是否在集合里。

于是就可以 DP（记忆化搜索）了。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-7;
const int N = 19, S = (1 << 18) + 10, INF = 0x3f3f3f3f;
int f[S];
int n, tmp, tot;

struct Point{
    double x, y;
}p[N];

struct Line{
    double a, b;
    int sta;
}l[N * N];

inline double F(double x, const Line &bd)
{
    return x * x * bd.a + x * bd.b;
}

inline bool OnLine(const Point &pg, const Line &bd)
{
    return fabs(F(pg.x, bd) - pg.y) < eps;
}

inline Line calc(const Point &p1, const Point &p2)
{
    double X1 = p1.x, X2 = p2.x, Y1 = p1.y, Y2 = p2.y;
    Line res;
    res.a = (Y2 * X1 - Y1 * X2) / (X1 * X2 * (X2 - X1));
    res.b = (Y1 - X1 * X1 * res.a) / X1;
    return res;
}

void init()
{
    for (int i = 0; i <= (1 << n); ++ i) f[i] = INF;
    tot = 0;
}

int main()
{
    int t;
    cin >> t;
    while (t --)
    {
        cin >> n >> tmp;
        init();
        for (int i = 0; i < n; ++ i) scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = 0; i < n; ++ i) l[++ tot].sta = (1 << i);
        for (int i = 0; i < n; ++ i)
            for (int j = i + 1; j < n; ++ j)
            {
                l[++ tot] = calc(p[i], p[j]);
                Line &now = l[tot];
                if (now.a > -eps)
                {
                    tot --;
                    continue;
                }
                for (int k = 0; k < n; ++ k)
                    if (OnLine(p[k], now)) now.sta |= 1 << k;
            }
        f[0] = 0;
        for (int i = 1; i <= tot; ++ i)
            for (int j = 0; j < (1 << n); ++ j)
                f[j | l[i].sta] = min(f[j | l[i].sta], f[j] + 1);
        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}