算法模版 动态规划

发表于 更新于 分类于 阅读次数： 本文字数： 3.6k
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int mod = 1e9 + 7;
struct Matrix {
    vector<vector<i64>> a;
    Matrix() { a.assign(3, vector<i64>(3)); }
    Matrix operator*(const Matrix b) const {
        Matrix res;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= 2; j++) {
                for (int k = 1; k <= 2; k++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return res;
    }
    void inita() { a[1][1] = a[1][2] = 1; }
    void initb() { a[1][1] = a[2][1] = a[1][2] = 1; }
};

Matrix qpow(Matrix a, i64 b) {
    Matrix res;
    for (int i = 1; i <= 2; i++) {
        res.a[i][i] = 1;
    }
    while (b) {
        if (b % 2 == 1) {
            res = res * a;
        }
        a = a * a;
        b /= 2;
    }
    return res;
}

void solve() {
    i64 n;
    cin >> n;
    if (n <= 2) {
        cout << 1 << "\n";
        return;
    }
    Matrix a, b;
    a.inita(), b.initb();
    a = a * qpow(b, n - 2);
    cout << a.a[1][1] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

数位 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

int dp[10][2];
int n, m, sz;
int c[10];
int dfs(int pos, bool sta, bool limit) {
    int ans = 0;
    if (pos == sz + 1) {
        return 1;
    }
    if (!limit && dp[pos][sta] != -1) {
        return dp[pos][sta];
    }
    int up = limit ? c[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (sta && i == 2) {
            continue;
        }
        if (i == 4) {
            continue;
        }
        ans += dfs(pos + 1, i == 6, limit && i == up);
    }
    if (!limit) {
        dp[pos][sta] = ans;
    }
    return ans;
}

void solve() {
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) {
            break;
        }
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i][j] = -1;
            }
        }
        string s = to_string(m);
        sz = s.size();
        s = " " + s;
        for (int i = 1; i <= sz; i++) {
            c[i] = s[i] - '0';
        }
        int ans = dfs(1, false, true);
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 2; j++) {
                dp[i][j] = -1;
            }
        }
        s = to_string(n - 1);
        sz = s.size();
        s = " " + s;
        for (int i = 1; i <= sz; i++) {
            c[i] = s[i] - '0';
        }
        ans -= dfs(1, false, true);
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

状态压缩

位运算基础

状态压缩是通过把状态压成一个数字而来的，如 5 个数 取 / 不取分别定义为 1 / 0，就可以用 10110 来表示一个状态，我们把这个二进制数看成十进制就是一个数字代表状态了，因此，位运算是极为关键的。

以下介绍了一些常见的位运算操作：

  1. 去掉最后一位 x >> 1
  2. 在最后面加一个零 x << 1
  3. 在最后面加一个一 (x << 1) | 1
  4. 将最后一位变为一 x | 1
  5. 将最后一位变为零 (x | 1) - 1
  6. 取第 \(k\) 位 (x >> (k - 1)) & 1
  7. 取末 \(k\)​ 位 x & ((1 << k) - 1)

二进制集合操作

一些状态压缩题是通过集合的形式进行的，因此需要掌握一些二进制集合的操作。

一个数的二进制可以看作是一个集合（ 0 表示不在集合中， 1 表示在集合中），那么可以通过位运算对集合进行的如下操作：

  1. 取交集： a & b
  2. 取并集： a | b
  3. 取补集： ~a（全集二进制都是 1 ）
  4. 取差集： a & (~b)
  5. 对称差（不同时在两个集合中的数）： a ^ b

子集遍历

遍历一个二进制数表示的集合的全部子集，等价于枚举二进制数对应掩码的所有子掩码。掩码是一串二进制码，用于和源码进行与运算，得到屏蔽源码的若干输入位后的新操作数，也就是说，通过枚举掩码从 0 到 \(n\) ，与原数 \(n\) 进行与运算，就可以遍历 \(n\) 二进制的子集。

但是，这样枚举会枚举到很多不需要的状态，例如与运算后全是 0，我们是不需要枚举的，因此有一种办法能降低枚举次数：

1
for(int s = n; s ; s = (s - 1) & m)

大致原理是：从最大的数每次减少 1，可以枚举所有子集，而减少 1 后进行与运算，可以跳过原数中连续的 0 ，使得每次减少 1 都是有意义的，因此，时间复杂度是 \(O(2^{\text{popcount(n)}})\)，取决于 \(n\) 二进制下 1 的个数。

遍历所有集合的子掩码

在状压 dp 中，很多时候对于集合类的问题，我们希望对于每个集合都遍历它所有子集，即对于每个掩码都遍历它的子掩码，代码如下（就是在上面的基础上再套一层循环）：

1
2
3
4
5
for(int i = 0; i<1<<m; i++) {
  	for(int j = i; j; j = (j - 1) & i) {
      	
    }
}

考虑集合中第 \(i\) 个元素（即二进制中第 \(i\) 位），有三种情况：

  1. 在掩码中为 0，因此在子掩码 \(s\) 中为 0，即元素不在大小子集中。
  2. 在掩码中为 1，但是在子掩码中为 0，即元素只在大子集中，不在小子集中。
  3. 在掩码和子掩码中都为 1，元素同时在大小子集中。

对于每一位都有以上三种情况，因此是 \(3^n\) 种组合，时间复杂度为 \(O(3^n)\)