抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

iznomia

钢铁洪流

博客

笔记

随笔

动态

源码

动态规划的状态设计

更新于 2023年4月1日

17k 字

89 分钟

次浏览

本文已经更新完毕，若有错误或需要补充的内容请在评论区留言。

动态规划的状态设计有许多值得探讨的内容。本文会从基本模型讲起，拓展到一些复杂的内容。

这里的基本模型并不会从基础开始，请确保你已经了解它们。

简单问题

这里的问题比较简单。

背包问题

这是一种很基础的模型，这里仅补充一个知识点。

方案数背包的撤回

其实之前已经见过这类问题，这里总结一下。

背包的添加物品很容易，但是删除物品很难。我们采用过前后缀合并的办法（但是需要枚举体积），也有线段树分治的做法。但是对于方案数背包，我们可以简单撤回：只需要减去当时加上的内容就行了。但是要注意循环顺序，应该是相反的。

区间 DP

最重要的特点是“合并”，如果题目有这种感觉，那么区间 DP 大概率是可做的。另外的知识点就是断环为链，可以高效解决环上的区间 DP 问题。

由于区间 DP 的常数很小（以下数据范围的循环次数约为 10910^9 次），所以在需要枚举断点（O(n3)O(n^3)）时，一般可以解决 2×1032\times 10^3 级别的问题；不需要枚举断点（从两头扩展，O(n2)O(n^2) 时），一般可以解决 5×1045\times 10^4 的问题。

区间 DP 也可以扩展到二维情况，此时一般会使用记忆化搜索实现，模板题可以参考 CF1198D，代码如下：

查看代码 
#include <bits/stdc++.h>
using namespace std;

int n;
int f[55][55][55][55];
char s[55][55];

int dfs(int x, int y, int _x, int _y) {
    if (f[x][y][_x][_y] != -1) return f[x][y][_x][_y];
    if (x == _x && y == _y) return f[x][y][_x][_y] = (s[x][y] == '#');
    int res = max(_x - x + 1, _y - y + 1);
    for (int i = x; i < _x; ++i) res = min(res, dfs(x, y, i, _y) + dfs(i + 1, y, _x, _y));
    for (int i = y; i < _y; ++i) res = min(res, dfs(x, y, _x, i) + dfs(x, i + 1, _x, _y));
    return f[x][y][_x][_y] = res; 
}

int main(void) {
    scanf("%d", &n); memset(f, -1, sizeof f);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    printf("%d\n", dfs(1, 1, n, n));
    return 0;
}

树形 DP

主要分为拓扑序问题和背包问题，对于子树的处理还会涉及到换根。在设计的时候，一定要注意子树的合并是每次加一个点还是一条边。

对于多次树形 DP，可以拍成 DFS 序进行优化。利用 DFS 序从大到小向父亲转移，可以很高效地实现树形 DP。

状压 DP

当难度上来之后，会发现状压 DP 相当麻烦。这里补充几个比较实用的知识点。

子集 DP

[NOIP2017 提高组] 宝藏。

设 f(i,j)f(i,j) 代表当前点集为 ii，树的最深节点到根节点的距离为 jj。枚举 ii 的子集，让不是它子集的那些都作为第 jj 层的儿子连接。枚举子集的子集的时间复杂度为 O(∑Cnk2k)=O(3n)O(\sum C_{n}^{k}2^k)=O(3^n) 级别。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int INF = 0x3f3f3f3f; 

int n, m, A[15][15];
int f[32770][17], v[32770]; // 点集为 i，深度为 j

int main(void) {
    scanf("%d%d", &n, &m); memset(A, 0x3f, sizeof(A));
    while (m--) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c); 
        --a; --b; A[a][b] = A[b][a] = min(A[a][b], c); 
    }
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i < n; ++i) f[1 << i][0] = A[i][i] = 0;
    for (int i = 1; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                for (int k = 0; k < n; ++k)
                    if (A[j][k] != INF) v[i] |= (1 << k);
    for (int i = 1; i < 1 << n; ++i)
        for (int s = i - 1 & i; s; s = s - 1 & i) if ((v[s] & i) == i) {
            int ss = s ^ i, sum = 0;
            for (int j = 0; j < n; ++j) if (ss & (1 << j)) {
                int tmp = INF;
                for (int k = 0; k < n; ++k) if (s & (1 << k))
                    tmp = min(tmp, A[j][k]);
                sum += tmp;
            }
            for (int j = 1; j < n; ++j) if (f[s][j - 1] != INF)
                f[i][j] = min(f[i][j], f[s][j - 1] + sum * j);
        }
    int ans = INF;
    for (int i = 0; i < n; ++i) ans = min(ans, f[(1 << n) - 1][i]);
    printf("%d\n", ans);
    return 0;
}

插头 DP

制毒大枭投掷了神秘的毒药。

将于未知的时间补充。

计数类 DP

严格来说，计数类 DP 不是 DP。动态规划是一类最优化问题，而计数类问题统计的是方案数，但是计数时要求“不重不漏”，需要精确的划分和整体性的计算，因此使用动态规划的子结构与多阶段可以高效的求解计数类 DP，实现上这种方法只能叫做递推。

其实计数 DP 会与很多组合方法综合，我们会见到的。

引子

我们做几道简单题，

[HAOI2010] 最长公共子序列

Portal.

求最长公共子序列已经很简单了，至于数量，就是要看它从哪里转移过来。设 g(i,j)g(i,j) 代表 A1…Ai,B1…BjA_1\dots A_i,B_1\dots B_j 的 LCS 个数，f(i,j)f(i,j) 代表 A1…Ai,B1…BjA_1\dots A_i,B_1\dots B_j 的 LCS 长度，那么：

  • 如果 g(i,j)g(i,j) 可以从 g(i−1,j)g(i-1,j) 转移过来，那么需要加上它的方案数；
  • 如果 g(i,j)g(i,j) 可以从 g(i,j−1)g(i,j-1) 转移过来，那么需要加上它的方案数；
  • 如果 g(i,j)g(i,j) 可以从 g(i−1,j−1)g(i-1,j-1) 转移过来，那么需要加上它的方案数。

但是如果前两条同时生效，那么会出现一个问题：f(i,j)=f(i−1,j)=f(i,j−1)f(i,j)=f(i-1,j)=f(i,j-1)，如果此时 f(i−1,j),f(i,j−1)f(i-1,j),f(i,j-1) 都可以从 f(i−1,j−1)f(i-1,j-1) 转移，那么这里就重复了，需要减去 g(i−1,j−1)g(i-1,j-1)。这种情况是什么时候？就是当上述的第三种转移没有生效的时候。也就是 f(i,j)=f(i−1,j−1)f(i,j) = f(i-1,j-1)，这样的话 f(i−1,j−1)=f(i−1,j)=f(i,j−1)f(i-1,j-1)=f(i-1,j)=f(i,j-1)，也就是说 f(i−1,j),f(i,j−1)f(i-1,j),f(i,j-1) 都可以从 f(i−1,j−1)f(i-1,j-1) 转移过来。

由于空间限制，所以要使用滚动数组。

查看代码 
// 由于这份代码的常数较大，可能需要吸氧才能过
#include <bits/stdc++.h>
#define i64 long long

using namespace std;

const int MOD = 100000000;

char a[5005], b[5005];
int n, m, f[2][5005];
i64 g[2][5005];

int main(void) {
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1) - 1, m = strlen(b + 1) - 1;
    for (int i = 0; i <= m; ++i) g[0][i] = 1;
    g[1][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            f[i & 1][j] = max({f[i & 1][j - 1], f[(i - 1) & 1][j], f[(i - 1) & 1][j - 1] + (a[i] == b[j])});
            g[i & 1][j] = 0;
            if (f[i & 1][j] == f[(i - 1) & 1][j]) g[i & 1][j] += g[(i - 1) & 1][j];
            if (f[i & 1][j] == f[i & 1][j - 1]) g[i & 1][j] += g[i & 1][j - 1];
            if (f[i & 1][j] == f[(i - 1) & 1][j - 1] + 1 && a[i] == b[j]) g[i & 1][j] += g[(i - 1) & 1][j - 1];
            if (f[i & 1][j] == f[(i - 1) & 1][j - 1]) g[i & 1][j] -= g[(i - 1) & 1][j - 1];

            g[i & 1][j] %= MOD;
        }
    printf("%d\n%lld\n", f[n & 1][m], g[n & 1][m]);
    return 0;
}

[CF149D] Coloring Brackets

Portal.

设 f(i,j,p,q)f(i,j,p,q) 为考虑区间 [i,j][i,j]，ii 的颜色为 pp，jj 的颜色为 qq 的方案数。转移也很好写，用 dfs 实现。

查看代码 
#include <bits/stdc++.h>
#define i64 long long
using namespace std;
const int MOD = 1000000007;

int n;
char s[705];
int match[705];
int f[705][705][3][3];

void dfs(int l, int r)
{
    #define rep(i) for (int i = 0; i <= 2; ++i)
    if (l + 1 == r)
    {
        f[l][r][0][1] = 1;
        f[l][r][0][2] = 1;
        f[l][r][1][0] = 1;
        f[l][r][2][0] = 1;
        return;
    }
    if (match[l] == r)
    {
        dfs(l + 1, r - 1);
        rep(i) rep(j)
        {
            if (i != 1) f[l][r][1][0] = (f[l][r][1][0] + f[l + 1][r - 1][i][j]) % MOD;
            if (i != 2) f[l][r][2][0] = (f[l][r][2][0] + f[l + 1][r - 1][i][j]) % MOD;
            if (j != 1) f[l][r][0][1] = (f[l][r][0][1] + f[l + 1][r - 1][i][j]) % MOD;
            if (j != 2) f[l][r][0][2] = (f[l][r][0][2] + f[l + 1][r - 1][i][j]) % MOD;
        }
        return;
    }
    dfs(l, match[l]), dfs(match[l] + 1, r);
    rep(i) rep(j) rep(p) rep(q)
    {
        if (j == p && j != 0) continue;
        f[l][r][i][q] = (f[l][r][i][q] + (i64)f[l][match[l]][i][j] * f[match[l] + 1][r][p][q]) % MOD;
    }
}

int main(void)
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    stack <int> st;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '(') st.push(i);
        else match[st.top()] = i, match[i] = st.top(), st.pop();
    }
    dfs(1, n);
    int ans = 0;
    for (int i = 0; i <= 2; ++i)
        for (int j = 0; j <= 2; ++j)
            ans = (ans + f[1][n][i][j]) % MOD;
    printf("%d\n", ans);
    return 0;
}

简单组合

组合数，组合方法这些对于读者来说一定不陌生。它们是与多阶段计数的最佳拍档。

[AHOI2009] 中国象棋

Portal.

显然每一行、每一列都最多只能有两个棋子。定义 f(i,j,k)f(i,j,k) 为考虑前 ii 行，有 jj 列是一个棋子，kk 列是两个棋子，剩下的 m−j−km-j-k 列没有棋子，显然计算时要满足 j+k≤mj+k\le m。

初始肯定 f(0,0,0)=1f(0,0,0)=1，接下来一行一行的考虑。

第 ii 行肯定可以什么都不放，所以我们用 f(i−1,j,k)f(i-1,j,k) 初始化 f(i,j,k)f(i,j,k)。

然后考虑第 ii 行放什么。显然要么放 11 个棋子，要么放 22 个棋子。

当放一个棋子的时候，这个棋子可以放在没有棋子的列，也可以放在有 11 个棋子的列。如果放在没有棋子的列，说明当前的 f(i,j,k)f(i,j,k) 是从 f(i−1,j−1,k)f(i-1,j-1,k) 过来的（多了一个有 11 个棋子的列），放的时候有 m−(j−1)−km-(j-1)-k 个空列，随便选一个即可。如果放在有一个棋子的列，说明当前的 f(i,j,k)f(i,j,k) 是从 f(i−1,j+1,k−1)f(i-1,j+1,k-1) 过来的（有一个棋子的少了一个，两个棋子的多了一个），选择时在 j+1j+1 个有一个棋子的列随便选一个即可。

当放两个棋子的时候，这两个棋子可以都放在没有棋子的列，这样它从 f(i−1,j−2,k)f(i-1,j-2,k) 过来的，放的时候的在 m−(j−2)−km-(j-2)-k 个空列中组合，共有 Cm−(j−2)−k2C_{m-(j-2)-k}^2 中可能；也可以都放在有一个棋子的列，从 f(i−1,j+2,k−2)f(i-1,j+2,k-2) 过来，有 Cm−(j+2)−k2C_{m-(j+2)-k}^2；还可以一个放在没有棋子的列，一个放在有一个棋子的列，从 f(i−1,j,k−1)f(i-1,j,k-1) 过来（一个放在没有棋子的列使得 j+1j+1，一个放在有一个棋子的列使得 j−1,k+1j-1,k+1，综合起来就是 jj 不变，k+1k+1），选择时放在没有棋子的列的选择有 m−j−(k−1)m-j-(k-1) 种，放在有一个棋子的列的选择有 jj 种。

可以使用滚动数组优化空间。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
using i64 = long long;

const int MOD = 9999973;

int n, m;
i64 f[2][105][105]; // 考虑前 i 行，有 j 列是一个棋子，k 列是两个棋子

int C(int n) {
    return (n * (n - 1)) / 2;
}

int main(void)
{
    scanf("%d%d", &n, &m);
    f[0][0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; j + k <= m; ++k)
            {
                f[i & 1][j][k] = f[(i - 1) & 1][j][k];
                if (/*m - j + 1 - k >= 0 && */j >= 1) f[i & 1][j][k] += f[(i - 1) & 1][j - 1][k] * (m - j + 1 - k); // 放一个棋子，放在没有棋子的列
                if (k >= 1) f[i & 1][j][k] += (f[(i - 1) & 1][j + 1][k - 1]) * (j + 1); // 放一个棋子在有一个棋子的列
                if (/*m - j + 2 - k >= 0 && */j >= 2) f[i & 1][j][k] += f[(i - 1) & 1][j - 2][k] * C(m - j + 2 - k); // 放两个棋子在都没有棋子的列
                if (k >= 2) f[i & 1][j][k] += f[(i - 1) & 1][j + 2][k - 2] * C(j + 2); // 放两个棋子在都有一个棋子的列
                if (/*m - j - k + 1 >= 0 && */k >= 1) f[i & 1][j][k] += f[(i - 1) & 1][j][k - 1] * j * (m - j - k + 1); // 放两个棋子，一个在有一个棋子的列，一个在没有棋子的列
                f[i & 1][j][k] %= MOD;
            }
    i64 ans = 0;
    for (int i = 0; i <= m; ++i)
        for (int j = 0; i + j <= m; ++j)
            ans = (ans + f[n & 1][i][j]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

[CF425E] Sereja and Sets

Portal.

设 f(r,i)f(r,i) 为右端点为 rr，时间为 ii 的方案数。转移采用刷表法。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int MOD = 1000000007;

int n, k;
i64 f[505][505], poww[250005];

int main(void) {
    scanf("%d%d", &n, &k);
    f[0][0] = 1;
    poww[0] = 1;
    for (int i = 1; i <= n * n; ++i) poww[i] = poww[i - 1] * 2 % MOD;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            for (int k = i + 1; k <= n; ++k)
                f[k][j + 1] = (f[k][j + 1] + f[i][j] * (poww[k - i] - 1) % MOD * poww[(n - k) * (k - i)]) % MOD;
    i64 ans = 0;
    for (int i = 0; i <= n; ++i)
        ans += f[i][k];
    printf("%lld\n", ans % MOD);
    return 0;
}

[NOIP2021] 数列

Portal.

给定整数 n,m,k(k≤n≤30,m≤100)n, m, k(k\le n\le 30,m\le 100)，和一个长度为 m+1m + 1 的正整数数组 v0,v1,…,vmv_0, v_1, \ldots, v_m。

对于一个长度为 nn，下标从 11 开始且每个元素均不超过 mm 的非负整数序列 {ai}\{a_i\}，我们定义它的权值为 va1×va2×⋯×vanv_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}。

当这样的序列 {ai}\{a_i\} 满足整数 S=2a1+2a2+⋯+2anS = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n} 的二进制表示中 11 的个数不超过 kk 时，我们认为 {ai}\{a_i\} 是一个合法序列。

计算所有合法序列 {ai}\{a_i\} 的权值和对 998244353998244353 取模的结果。

SS 在统计时是会进位的，因此我们设 f(i,j,k,p)f(i,j,k,p) 代表考虑 SS 从低位开始的前 ii 位，考虑了 jj 个数（任意），有 kk 个 11（由于是加法，11 只能变多不能变少），向下一位的进位为 pp（状态中的 SS 按照二进制考虑，第 ii 位有 pp 个 11，很显然这样压根就没有考虑进位，进位是在转移的时候进行的）。显然初始时有 f(0,0,0,0)=1f(0,0,0,0)=1，接下来考虑如何转移。

显然刷表法会更容易一些。假设再给序列 aa 选择 tt 个元素 ii，那么 SS 的第 ii 位就会加上 tt 个 11，总共就有了 t+pt+p 个 11。同时我们要将第 ii 位进行“展平”，也就是向前进位。如果 t+pt+p 是奇数，那么 11 的个数就多了 11，否则没变；向前进位的个数为 ⌊t+p2⌋\left\lfloor\cfrac{t+p}{2}\right\rfloor。也就是说，f(i,j,k,p)f(i,j,k,p) 转移到了：

f(i+1,j+t,k+(t+p) mod 2,⌊t+p2⌋)f\left(i+1,j+t,k+(t+p)\bmod 2,\left\lfloor\frac{t+p}{2}\right\rfloor\right)

贡献是多少？基数是 f(i,j,k,p)f(i,j,k,p)，这种转移共有 (n−jt)\dbinom{n-j}{t} 个 vitv_i^t 种方式（在还没有填的 aa 中选出 tt 个来填），单次的贡献是 vitv_i^t，所以贡献为 vit×(n−jt)v_i^t\times \dbinom{n-j}{t}。

统计答案时判断一下 11 的个数是否合法即可（要加上进位的）。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
const int MOD = 998244353;

int n, m, K;
int C[35][35], v[105][55];
int f[105][35][35][35];

int count(int x) {
    int res = 0;
    for (;x ; x >>= 1) res += (x & 1);
    return res;
}

int main(void) 
{
    scanf("%d%d%d", &n, &m, &K);
    C[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
    for (int i = 0; i <= m; ++i) {
        v[i][0] = 1;
        scanf("%d", &v[i][1]);
        for (int j = 2; j <= n; ++j) v[i][j] = 1ll * v[i][j - 1] * v[i][1] % MOD;
    }
    
    f[0][0][0][0] = 1;
    for (int i = 0; i <= m; ++i)
      for (int j = 0; j <= n; ++j)
        for (int k = 0; k <= K; ++k)
          for (int p = 0; p <= n >> 1; ++p)
            for (int t = 0; t <= n - j; ++t) {
                int &dp = f[i + 1][j + t][k + ((t + p) & 1)][(t + p) >> 1];
                dp = (dp + 1ll * f[i][j][k][p] * v[i][t] % MOD * C[n - j][t]) % MOD;
            }
    
    int ans = 0;
    for (int k = 0; k <= K; ++k)
        for (int p = 0; p <= n >> 1; ++p)
            if (k + count(p) <= K) ans = (ans + f[m + 1][n][k][p]) % MOD;
    printf("%d\n", ans);
    return 0;
}

数位统计 DP

简称数位 DP。用于解决一类与数字相关，一般是给定一些限制条件，然后询问满足条件的第 kk 小数是多少，或者是有多少个满足条件的数的题目。

概述

将数字按每一位拆开，比如最常用的十进制，拆完之后每一位数字都是 0∼90\sim 9。问题具有以下特征：

  • 计数，统计数的数量；
  • 数的值域很大；
  • 可以使用”数位“来理解……

比如说 james1 数数，数 100∼199100\sim 199 和 200∼299200\sim 299 几乎一致，00∼9900\sim 99 这一部分是完全一样的。这样就可以根据此设计状态来求解问题。

很多时候为了计算方便我们都会先允许前导 00 的存在，最后再减去。

简单题

我们来看一些简单的题目来进一步认识数位 DP。

[ZJOI2010] 数字计数

Portal.

给定两个正整数 aa 和 bb，求在 [a,b][a,b] 中的所有整数中，每个数码各出现了多少次，1≤a≤b≤10121\le a\le b\le 10^{12}。

设 f(i)f(i) 代表满 ii 位数的每个数字的出现个数，即 0∼10i−10\sim 10^i-1 中的每个数字的出现个数，假定可以有前导零，那么每个数字的出现次数是相等的。前 i−1i-1 位的数字贡献是 10f(i−1)10f(i-1)，第 ii 位的数字贡献是 10i−110^{i-1}。

现在考虑如何统计答案。我们肯定是求两个前缀和然后相减。求前缀和时将上界从高到低位枚举，不贴着上界时后面可以随便取，贴着时只能取到上界。如果有前导零还需要减去。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

i64 l, r;
i64 f[15], poww[15];
i64 ans1[15], ans2[15];

void calc(i64 n, i64 *ans)
{
    static int a[15];
    int len = 0; i64 tmp = n;
    while (tmp) a[++len] = tmp % 10, tmp /= 10;
    for (int i = len; i >= 1; --i) {
        // 首先考虑后 i - 1 位的贡献
        for (int j = 0; j < 10; ++j) ans[j] += f[i - 1] * a[i]; // 满 i-1 位的数字，有 a[i] 个（不算以 0 打头，因为下一位的时候会考虑）
        // 再考虑第 i 位的贡献
        for (int j = 0; j < a[i]; ++j) ans[j] += poww[i - 1]; // 0 ~ a[i]-1 都会出现 10^(i-1) 次
        n -= poww[i - 1] * a[i]; // 减掉第 i 位，剩下的数字
        ans[a[i]] += n + 1; // a[i] 会在 0~n 出现一次
        // 最后处理前导零
        ans[0] -= poww[i - 1]; // 当第 i 位为 0 时，答案就没有意义，此时剩下的可以随便填，仅有这部分的零不会出现
    }
}

int main(void)
{
    cin >> l >> r;
    poww[0] = 1;
    for (int i = 1; i <= 13; ++i) {
        f[i] = f[i - 1] * 10 + poww[i - 1]; 
        poww[i] = poww[i - 1] * 10;
    }
    calc(r, ans1); calc(l - 1, ans2);
    for (int i = 0; i < 10; ++i)
        printf("%lld ", ans1[i] - ans2[i]);
    putchar('\n');
    return 0;
}

[CQOI2016] 手机号码

Portal.

数位 DP 一般采用记忆化搜索实现。直接将所有信息记录下来，暴力枚举每一位的数字。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int num[15];
int f[11][11][11][2][2][2][2];

i64 dp(int p, int p1, int p2, bool lim, bool d, bool _4, bool _8) {
    if (_4 && _8) return 0;
    if (p == 0) return d;
    if (f[p][p1][p2][lim][d][_4][_8] != -1) return f[p][p1][p2][lim][d][_4][_8];
    i64 res = 0; int mx = lim ? 9 : num[p];
    for (int i = 0; i <= mx; ++i)
        res += dp(p - 1, i, p1, lim || (i < mx), d || (i == p1 && i == p2), _4 || (i == 4), _8 || (i == 8));
    return f[p][p1][p2][lim][d][_4][_8] = res;
}

i64 calc(i64 n) {
    memset(f, 0xff, sizeof f);
    for (int i = 1; i <= 11; ++i, n /= 10) num[i] = n % 10;
    i64 res = 0;
    for (int i = 1; i <= num[11]; ++i) 
        res += dp(10, i, -1, i < num[11], 0, i == 4, i == 8);
    return res;
}

int main(void) {
    i64 l, r; cin >> l >> r; cout << calc(r) - calc(l - 1) << "\n";
    return 0;
}

矩阵优化 DP

很多 DP 问题可以通过矩阵优化。

矩阵快速幂优化

矩阵快速幂可以加速递推，可以加速每一轮的转移都相同的转移方程。

[CF222E] Decoding Genome.

设 fi,jf_{i,j} 代表考虑到第 ii 个字符，此字符为 jj 的方案数。发现转移是一个矩阵乘法的形式，因此可以使用矩阵快速幂优化。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int P = 1000000007;

struct Matrix {
    int a[52][52];
    Matrix() { memset(a, 0, sizeof(a)); }
    friend Matrix operator * (const Matrix &a, const Matrix &b) {
        Matrix c;
        for (int i = 0; i < 52; ++i)
            for (int k = 0; k < 52; ++k) {
                int r = a.a[i][k];
                for (int j = 0; j < 52; ++j)
                    c.a[i][j] = (c.a[i][j] + 1ll * r * b.a[k][j]) % P; 
            }
        return c;
    }
};
Matrix poww(Matrix a, i64 b) {
    Matrix res = a; --b; 
    for (; b; b >>= 1, a = a * a) if (b & 1) res = res * a;
    return res;
}

i64 n;
int m, k;

int H(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A' + 26;
}

int main(void) {
    ios::sync_with_stdio(false); cin >> n >> m >> k;
    if (n == 1) return cout << m << "\n", 0;
    Matrix f, a; 
    for (int i = 0; i < m; ++i) for (int j = 0; j < m; ++j) f.a[i][j] = 1; 
    for (int i = 0; i < m; ++i) a.a[0][i] = 1; 
    for (int i = 1; i <= k; ++i) {
        char x, y; cin >> x >> y;
        f.a[H(x)][H(y)] = 0;
    }
    a = a * poww(f, n - 1);
    int ans = 0;
    for (int i = 0; i < m; ++i) ans = (ans + a.a[0][i]) % P;
    return cout << ans << "\n", 0;
}

动态 DP

本来是指一类解决树上带权修改的 DP 问题，但是笔者认为利用数据结构维护广义矩阵乘法来进行 DP 的都应该属于“动态” DP。

Portal.

给定一棵 nn 个点的点权树，支持修改点的点权，查询树最大独立集的权值大小。

依然设 fi,1/0f_{i,1/0} 代表对于 ii 的子树是否选则第 ii 个节点，子树内的独立集最大大小。

如何支持修改？对原树进行重链剖分，设 gi,1/0g_{i,1/0} 代表 ii 的子树不考虑重儿子的情况下的答案。有：

fi,0=gi,0+max⁡{fsoni,0,fsoni,1}fi,1=gi,1+fsoni,0f_{i,0}=g_{i,0}+\max\{f_{son_i,0},f_{son_i,1}\}\\ f_{i,1}=g_{i,1}+f_{son_i,0}

我们定义另一种矩阵乘法：

Ci,j=max⁡k=1nAi,k+Bk,jC_{i,j}=\max_{k=1}^n A_{i,k}+B_{k,j}

则有：

[fsoni,0fsoni,1]×[gi,0gi,1gi,0−∞]=[fi,0fi,1]\begin{bmatrix} f_{son_i,0} & f_{son_i,1} \end{bmatrix}\times \begin{bmatrix} g_{i,0} & g_{i,1}\\ g_{i,0} & -\infty \end{bmatrix}= \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix}

这样在一条重链上就可以直接用线段树维护答案，我们只需要保证含 11 的那条链上的东西都是对的就行了（我们只需要保证 11 的答案正确，剩下的让它自生自灭即可）。

我们相当于从一个权值为 00 的叶子节点开始 DP，注意 DFS 序大的应该先乘，所以线段树的维护顺序应该是从右到左。修改时，当前节点的 gi,1g_{i,1} 会改变，然后直接考虑重链顶端父亲的答案改变，改的是当前节点的一个轻儿子，计算改变量即可。

查看代码 
#include <bits/stdc++.h>
using namespace std; 
const int INF = 1e9; 

int n, m, a[100005], f[100005][2]; 
int siz[100005], son[100005], fa[100005]; 
int top[100005], L[100005], R[100005], num, idx[100005]; 
vector<int> G[100005]; 
struct Matrix {
    int a[2][2]; 
    Matrix() { memset(a, 0, sizeof a); }
    friend Matrix operator* (const Matrix &a, const Matrix &b) {
        Matrix c; 
        for (int i = 0; i < 2; ++i) for (int k = 0; k < 2; ++k) {
            int r = a.a[i][k]; 
            for (int j = 0; j < 2; ++j)
                c.a[i][j] = max(c.a[i][j], r + b.a[k][j]); 
        }
        return c; 
    }
} T[400005], g[100005]; 

void build(int o, int l, int r) {
    if (l == r) return T[o] = g[idx[l]], void(); 
    int mid = l + r >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 
    T[o] = T[o << 1 | 1] * T[o << 1]; 
}
void update(int o, int l, int r, int x) {
    if (l == r) return T[o] = g[idx[l]], void(); 
    int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x); 
    else update(o << 1 | 1, mid + 1, r, x); 
    T[o] = T[o << 1 | 1] * T[o << 1]; 
}
Matrix query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o]; 
    int mid = l + r >> 1; 
    if (y <= mid) return query(o << 1, l, mid, x, y); 
    if (mid < x) return query(o << 1 | 1, mid + 1, r, x, y); 
    return query(o << 1 | 1, mid + 1, r, x, y) * query(o << 1, l, mid, x, y); 
}

void dfs(int x, int fa) {
    siz[x] = 1; ::fa[x] = fa; f[x][1] = a[x]; 
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); siz[x] += siz[y]; 
        if (siz[y] > siz[son[x]]) son[x] = y; 
        f[x][1] += f[y][0]; 
        f[x][0] += max(f[y][0], f[y][1]); 
    }
}
void dfs2(int x, int topf) {
    idx[L[x] = ++num] = x; R[top[x] = topf] = num; 
    g[x].a[0][1] = a[x]; g[x].a[1][1] = -INF; 
    if (!son[x]) return; dfs2(son[x], topf); 
    for (int y : G[x]) if (y != son[x] && y != fa[x]) {
        dfs2(y, y); 
        g[x].a[0][1] += f[y][0]; 
        g[x].a[0][0] += max(f[y][0], f[y][1]); 
    }
    g[x].a[1][0] = g[x].a[0][0]; 
}

void update(int x, int k) {
    g[x].a[0][1] += k - a[x]; a[x] = k; 
    while (x) {
        int y = top[x]; Matrix lst = query(1, 1, n, L[y], R[y]); 
        update(1, 1, n, L[x]); Matrix now = query(1, 1, n, L[y], R[y]); 
        x = fa[y]; 
        g[x].a[0][0] += max(now.a[0][0], now.a[0][1]) - max(lst.a[0][0], lst.a[0][1]); 
        g[x].a[1][0] = g[x].a[0][0]; 
        g[x].a[0][1] += now.a[0][0] - lst.a[0][0]; 
    }
}

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } dfs(1, 0); dfs2(1, 1); build(1, 1, n); 
    while (m--) {
        int x, k; scanf("%d%d", &x, &k); update(x, k); 
        Matrix ans = query(1, 1, n, L[1], R[1]); 
        printf("%d\n", max(ans.a[0][0], ans.a[0][1])); 
    }
    return 0;
}

自动机上 DP

难度较大。在学习之前，推荐学习一些自动机的知识（而且不难）。即使是 DP 套 DP，从自动机的角度理解也是有益的，甚至是最好理解的。

KMP 自动机上 DP

[CF1163D] Mysterious Code.

找一个模式串在字符串中的出现次数，而看到可以在 * 上填任意一个字母又是经典 DP 问题。对 s,ts,t 建出 KMP 自动机，设 f(i,j,k)f(i,j,k) 考虑到 cc 的第 ii 位，此时在 ss 的 KMP 自动机的节点 jj，tt 的 KMP 自动机的节点 kk 的最大答案。采用刷表法转移，模式串 SS 在转移到节点 ∣S∣|S| 时有贡献。初始 f(0,0,0)=0f(0,0,0)=0，转移 f(i+1,trsj,ci+1,trtk,ci+1)=max⁡{f(i,j,k)+w}f(i+1,trs_{j,c_{i+1}},trt_{k,c_{i+1}})=\max\{f(i,j,k)+w\}，目标 max⁡{f(n,j,k)}\max\{f(n,j,k)\}。

查看代码 
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)

using namespace std;

int n, ls, lt, nxts[55], nxtt[55], trs[55][26], trt[55][26];
char a[1005], s[55], t[55];
int f[1005][55][55];

void KMP(char *s, int len, int *nxt, int tr[][26]) {
    for (int i = 2, p = 0; i <= len; ++i) {
        while (p && s[i] != s[p + 1]) p = nxt[p];
        if (s[i] == s[p + 1]) ++p;
        nxt[i] = p;
    }
    rep(i, 0, len) rep(j, 0, 25) {
        if (i < len && s[i + 1] == j + 'a') tr[i][j] = i + 1; 
        else if (i) tr[i][j] = tr[nxt[i]][j];
    }
}
void ckmax(int &x, int t) { if (x < t) x = t; }

int main(void) {
    scanf("%s%s%s", a + 1, s + 1, t + 1);
    n = strlen(a + 1); ls = strlen(s + 1); lt = strlen(t + 1);
    KMP(s, ls, nxts, trs); KMP(t, lt, nxtt, trt);
    memset(f, 0xbf, sizeof f); f[0][0][0] = 0;
    rep(i, 0, n - 1) rep(j, 0, ls) rep(k, 0, lt) rep(p, 0, 25) if (a[i + 1] == '*' || a[i + 1] == p + 'a') {
        int w = 0;
        if (trs[j][p] == ls) ++w; if (trt[k][p] == lt) --w; 
        ckmax(f[i + 1][trs[j][p]][trt[k][p]], f[i][j][k] + w);
    }
    int ans = -1e9;
    rep(i, 0, ls) rep(j, 0, lt) ans = max(ans, f[n][i][j]);
    return printf("%d\n", ans), 0;
}

DP 套 DP

本质上就是内层 DP 的结果作为外层 DP 的状态，内层压的东西一般可以看成一个 bool 数组，表示外层的状态是否能够取到。这样状态数可能很多，所以往往需要以实际搜出来的结果为准。

[TJOI2018] 游园会。

求长度为 nn，字符集为 N,O,I\text{N,O,I}，且不能出现子串 NOI\text{NOI}，与给定字符串 SS 的 LCS 为 lenlen（需要求出所有的 lenlen 对应的答案）的长度。n≤1000,∣S∣≤15n\le 1000, |S|\le 15。

LCS 是什么？像这样：

LCSx,y={LCSx−1,y−1+1,Ax=By,max⁡{LCSx−1,y,LCSx,y−1},Ax≠By.\text{LCS}_{x,y}= \begin{cases} \text{LCS}_{x-1,y-1}+1&,A_x=B_y,\\ \max\{\text{LCS}_{x-1,y},\text{LCS}_{x,y-1}\}&,A_x\neq B_y.\\ \end{cases}

我们对 LCS 取一遍前缀最大值。把这个 LCS 的 DP 数组作为状态压进 DP（当其中一维固定时，LCS 数组的前缀最大值差分后可以得到一个 01 序列，状压后就可以压进去）。这相当于自动机上的一个点，枚举出满足不出现子串 NOI 的字符作为自动机的转移，计算出转移到的自动机上的点并更新方案数。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;

int n, k, ans[20], a[20], b[20]; // LCS(i, ...)
char s[20];
int f[2][35005][3]; // 考虑到字符串的第 i 位，当前 "NOI" 子串的长度为 k

void decode(int *a, int ret) {
    for (int i = 0; i < k; ++i) a[i + 1] = (ret >> i & 1) + a[i];
}
int encode(int *a) {
    int ret = 0;
    for (int i = 0; i < k; ++i) ret |= (a[i + 1] - a[i]) << i;
    return ret;
}
void dp(int now, int t, int p, char c, int w) {
    decode(a, t);
    for (int i = 1; i <= k; ++i) b[i] = max({b[i - 1], a[i], a[i - 1] + (c == s[i])});
    t = encode(b); f[now][t][p] = (f[now][t][p] + w) % P;
}

int main(void) {
    scanf("%d%d%s", &n, &k, s + 1); f[0][0][0] = 1; 
    for (int i = 0; i < n; ++i) {
        memset(f[i - 1 & 1], 0, sizeof(f[i - 1 & 1]));
        for (int j = 0; j < 1 << k; ++j) {
            if (f[i & 1][j][0]) {
                dp(i - 1 & 1, j, 1, 'N', f[i & 1][j][0]);
                dp(i - 1 & 1, j, 0, 'O', f[i & 1][j][0]);
                dp(i - 1 & 1, j, 0, 'I', f[i & 1][j][0]);
            }
            if (f[i & 1][j][1]) {
                dp(i - 1 & 1, j, 1, 'N', f[i & 1][j][1]);
                dp(i - 1 & 1, j, 2, 'O', f[i & 1][j][1]);
                dp(i - 1 & 1, j, 0, 'I', f[i & 1][j][1]);
            }
            if (f[i & 1][j][2]) {
                dp(i - 1 & 1, j, 1, 'N', f[i & 1][j][2]);
                dp(i - 1 & 1, j, 0, 'O', f[i & 1][j][2]);
            }
        }
    }
    for (int i = 0; i < 1 << k; ++i) for (int j = 0; j < 3; ++j) {
        int &x = ans[__builtin_popcount(i)];
        x = (x + f[n & 1][i][j]) % P;
    }
    for (int i = 0; i <= k; ++i) printf("%d\n", ans[i]);
    return 0;
}

可以发现 DP 套 DP 就是在一个 DP 自动机上进行 DP。其有一些技巧，请参考 Problemset。

Problemset

前面的题主要是单个知识点为主的模型，后面会出现超级大杂题。

背包问题

很有意思！后面有些题相当麻烦。

[HNOI2007] 梦幻岛宝珠

Portal.

考虑对 2b2^b 中 bb 相同的物品进行分层 DP，设 f(i,j)f(i,j) 表示考虑到 2i2^i 的物品，恰好剩余 j×2ij\times 2^i 的体积时能够取得的最大价值。同层的转移直接使用 01 背包，从高层开始转移，不同层则是 f(i−1,j×2+si−1)←f(i,j)f(i-1,j\times 2+s_{i-1})\leftarrow f(i,j)，其中 si−1s_{i-1} 代表 WW 二进制下的第 i−1i-1 位。

查看代码 
#include <bits/stdc++.h>
using namespace std;
void ckmax(int &a, int b) { if (a < b) a = b; }

int n, W, t;
int f[35][1005], s[35];
int w[105], v[105];
vector<int> a[35];

int main(void) {
    while (scanf("%d%d", &n, &W) == 2 && n != -1) {
        memset(f, 0xbf, sizeof(f)); memset(s, 0, sizeof(s)); 
        memset(a, 0, sizeof(a));
        for (int j = 0; j <= 30; ++j) if ((W >> j) & 1) s[t = j] = 1;

        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", w + i, v + i);
            int b = 0;
            while (w[i] % 2 == 0) w[i] >>= 1, ++b;
            a[b].emplace_back(i);
        }
        int ans = 0;
        for (int i = t; i >= 0; --i) {
            f[i][s[i]] = max(f[i][s[i]], 0);
            for (auto k : a[i])
                for (int j = w[k]; j <= 1000; ++j)
                    ckmax(f[i][j - w[k]], f[i][j] + v[k]);
            if (i > 0) {
                for (int j = 0; j <= 1000; ++j)
                    ckmax(f[i - 1][min(1000, j * 2 + s[i - 1])], f[i][j]);
            } else {
                for (int j = 0; j <= 1000; ++j)
                    ckmax(ans, f[i][j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

[Luogu P8564] ρars/ey

Portal.

树形背包。在背包进行完之后，要统计删除当前子树的代价。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int n, v[5005], siz[5005];
i64 f[5005][5005]; // x 为根，删除 i 个点
vector<int> G[5005];

void dfs(int x, int fa) {
    siz[x] = 1; f[x][0] = 0; int s = 0;
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); s += siz[y];
        for (int i = s - 1; i >= 0; --i)
            for (int j = min(i, siz[y] - 1); j >= max(1, i - siz[x]); --j)
                f[x][i] = min(f[x][i], f[x][i - j] + f[y][j]);
        siz[x] += siz[y];
    }
    for (int i = 0; i < siz[x] - 1; ++i)
        f[x][siz[x] - 1] = min(f[x][siz[x] - 1], f[x][i] + v[siz[x] - i]);
}

int main(void) {
    scanf("%d", &n); memset(f, 0x3f, sizeof(f));
    for (int i = 2; i <= n; ++i) scanf("%d", v + i);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    dfs(1, 0);
    printf("%lld\n", f[1][n - 1]);
    return 0;
}

[十二省联考 2019] 皮配

Portal.

考虑 K=0K=0 怎么做。分别考虑划分两种特征，两次背包分别对工具箱和螺丝进行 DP 即可。

发现 KK 很小，考虑针对它设计状态。对于不是这 KK 个没事找事的螺丝，前面的 DP 做法依然成立。然后再考虑这些没事找事的。

设 f(i,j,k)f(i,j,k) 代表考虑前 ii 个物品，普通螺钉的重量为 jj，三角螺纹的重量为 kk。需要枚举当前的选的东西是什么，因此再记一个 gg 表示自攻方螺钉。滚掉 ii 这一维，所有状态都是可以转移的，考虑用这种方式处理没事找事的螺丝，时间复杂度为 O(k2wM)O(k^2 w M)。

然后枚举体积，进行背包合并即可。

查看代码 
#include <bits/stdc++.h>
#define mem(x, v) memset(x, v, sizeof x)
using namespace std; 
const int P = 998244353; 
inline void add(int &x, int t) { x = (x + t) % P; }

int n, c, C0, C1, D0, D1; 
int b[2505], w[2505], ban[2505], vis[2505]; 
int f[2505], g[2505]; // 普通 / 三角 为 i 的方案数
int F[2505][2505], G[2505][2505]; 
int siz[2505]; 

void solve(void) {
    mem(siz, 0); mem(vis, 0); mem(ban, -1); 

    cin >> n >> c >> C0 >> C1 >> D0 >> D1; int ALL = 0; 
    for (int i = 1; i <= n; ++i) cin >> b[i] >> w[i], siz[b[i]] += w[i], ALL += w[i]; 
    int K; cin >> K; 
    for (int x; K--; ) cin >> x, cin >> ban[x], vis[b[x]] = 1; 

    mem(f, 0); f[0] = 1; 
    for (int i = 1; i <= c; ++i) if (!vis[i] && siz[i])
        for (int j = C0; j >= siz[i]; --j) add(f[j], f[j - siz[i]]); 
    for (int i = 1; i <= C0; ++i) add(f[i], f[i - 1]); 
    mem(g, 0); g[0] = 1; 
    for (int i = 1; i <= n; ++i) if (ban[i] == -1)
        for (int j = D0; j >= w[i]; --j) add(g[j], g[j - w[i]]); 
    for (int i = 1; i <= D0; ++i) add(g[i], g[i - 1]); 

    mem(F, 0); mem(G, 0); F[0][0] = 1; 
    int Cs = 0, Ds = 0; 
    for (int op = 1; op <= c; ++op) if (vis[op]) {
        Cs += siz[op]; Cs = min(Cs, C0); 
        for (int i = 0; i <= Cs; ++i) for (int j = 0; j <= Ds; ++j) G[i][j] = F[i][j]; 
        for (int x = 1; x <= n; ++x) if (b[x] == op && ban[x] != -1) {
            Ds += w[x]; Ds = min(Ds, D0); 
            // 0 不是 普通三角
            // 1 不是 普通方
            // 2 不是 自攻三角
            // 3 不是 自攻方
            // F 普通三角 G 自攻方
            if (ban[x] == 1) {
                for (int i = 0; i <= Cs; ++i) {
                    for (int j = Ds; j >= w[x]; --j) F[i][j] = F[i][j - w[x]]; 
                    for (int j = w[x] - 1; j >= 0; --j) F[i][j] = 0; 
                }
            }
            if (ban[x] >= 2) {
                for (int i = 0; i <= Cs; ++i)
                    for (int j = Ds; j >= w[x]; --j)
                        add(F[i][j], F[i][j - w[x]]); 
            }
            if (ban[x] == 3) {
                for (int i = 0; i <= Cs; ++i) {
                    for (int j = Ds; j >= w[x]; --j) G[i][j] = G[i][j - w[x]]; 
                    for (int j = w[x] - 1; j >= 0; --j) G[i][j] = 0; 
                }
            }
            if (ban[x] <= 1) {
                for (int i = 0; i <= Cs; ++i)
                    for (int j = Ds; j >= w[x]; --j)
                        add(G[i][j], G[i][j - w[x]]); 
            }
        }
        for (int j = 0; j <= Ds; ++j) {
            for (int i = Cs; i >= siz[op]; --i) F[i][j] = F[i - siz[op]][j]; 
            for (int i = siz[op] - 1; i >= 0; --i) F[i][j] = 0; 
        }
        for (int i = 0; i <= Cs; ++i) for (int j = 0; j <= Ds; ++j) add(F[i][j], G[i][j]); 
    }

    int ans = 0; 
    for (int i = 0; i <= Cs; ++i) for (int j = 0; j <= Ds; ++j) {
        int l1 = max(0, ALL - C1 - i), r1 = C0 - i; if (l1 > r1) continue; 
        int l2 = max(0, ALL - D1 - j), r2 = D0 - j; if (l2 > r2) continue; 
        int v1 = f[r1] - (l1 ? f[l1 - 1] : 0), v2 = g[r2] - (l2 ? g[l2 - 1] : 0); 
        add(ans, 1ll * v1 * v2 % P * F[i][j] % P); 
    }
    cout << (ans + P) % P << "\n"; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    int T; cin >> T; 
    while (T--) solve(); 
    return 0; 
}

区间 DP

也可以变得相当复杂。

[CF1572C] Paint

Portal.

设 f(i,j)f(i,j) 代表将 [i,j][i,j] 染成 cjc_j 的代价（想一想这样为什么是正确的），当 ck=cjc_k=c_j 时有 f(i,j)=f(i,k)+f(k+1,j)f(i,j)=f(i,k)+f(k+1,j)。

查看代码 
#include <bits/stdc++.h>
using namespace std;

int n, p[3005], pre[3005];
int a[3005], f[3005][3005];

void solve(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) {
        p[i] = pre[i] = 0;
        for (int j = i; j <= n; ++j) f[i][j] = 1e9;
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i); f[i][i] = 0;
        if (p[a[i]]) pre[i] = p[a[i]]; p[a[i]] = i;
    }
    for (int len = 2; len <= n; ++len)
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            f[i][j] = min(f[i][j - 1], f[i + 1][j]) + 1;
            for (int k = pre[j]; k >= i; k = pre[k])
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
        }
    printf("%d\n", f[1][n]);
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

[CERC2014] Outer space invaders

Portal.

在时间上进行区间 DP，合并时要找到这一时间段中距离最远的外星人，枚举它在哪一个时间点被摧毁。

查看代码 
#include <bits/stdc++.h>
using namespace std;

int n, m, C[605];
int f[605][605];
struct enemy {
    int a, b, d;
    void rd(void) { scanf("%d%d%d", &a, &b, &d); C[++m] = a; C[++m] = b; }
} a[305];

void solve(void) {
    scanf("%d", &n); m = 0; for (int i = 1; i <= n; ++i) a[i].rd(); 
    sort(C + 1, C + m + 1); m = unique(C + 1, C + m + 1) - (C + 1);
    for (int i = 1; i <= n; ++i) {
        a[i].a = lower_bound(C + 1, C + m + 1, a[i].a) - C;
        a[i].b = lower_bound(C + 1, C + m + 1, a[i].b) - C;
    }
    for (int i = 1; i <= m; ++i) fill(f[i] + 1, f[i] + m + 1, 0);
    for (int len = 2; len <= m; ++len)
        for (int i = 1; i <= m - len + 1; ++i) {
            int j = i + len - 1, mx = 0, t = -1;
            for (int k = 1; k <= n; ++k)
                if (a[k].a >= i && a[k].b <= j && mx < a[k].d) mx = a[t = k].d; 
            if (t == -1) continue;
            f[i][j] = 1e9;
            for (int k = a[t].a; k <= a[t].b; ++k)
                f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + mx);
        }
    printf("%d\n", f[1][m]);
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

树形 DP

是基础 DP 中比较复杂的一类。

[HEOI2013] SAO

Portal.

给定一张树状结构的有向图，求其拓扑序的数量。

设 f(x,i)f(x,i) 代表考虑 xx 的子树，考虑 ii 个节点的拓扑序数量，初始时 f(x,1)=1f(x,1)=1，目标为 ∑i=1nf(1,i)\sum_{i=1}^n f(1,i)。

以 yy 在 xx 前面的转移为例。枚举 j∈[1,siz[y]]j\in[1,siz[y]] 为在 yy 中选取的在 xx 前的个数，转移方程为：

f(x,i+j)⟵+∑k=1jf(x,i)×f(y,k)×(i+j−1j)×(siz[x]−i+siz[y]−jsiz[x]−i)f(x,i+j)\stackrel{+}{\longleftarrow} \sum_{k=1}^{j} f(x,i)\times f(y,k)\times \binom{i+j-1}{j}\times \binom{siz[x]-i+siz[y]-j}{siz[x]-i}

其意义不难理解，后面两个组合数分别是在 ii 的后代中选择 jj 个位置、没有选择的随便排。处理一个前缀和就可以快速转移了。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int P = 1000000007;

int n, siz[1005];
i64 C[1005][1005], f[1005][1005], g[1005];
vector<pair<int, bool>> G[1005];

inline void addedge(int u, int v, bool w) {
    G[u].emplace_back(make_pair(v, w));
    G[v].emplace_back(make_pair(u, !w));
}
void add(i64 &x, int t) { x = (x + t) % P; }

void dfs(int x, int fa) {
    siz[x] = 1; f[x][1] = 1; 
    for (auto [y, w] : G[x]) if (y != fa) {
        dfs(y, x); 
        memcpy(g, f[x], sizeof(g)); memset(f[x], 0, sizeof(f[x]));
        if (w) {
            for (int i = 1; i <= siz[x]; ++i)
                for (int j = 0; j < siz[y]; ++j)
                    add(f[x][i + j], g[i] * C[i + j - 1][j] % P * C[siz[x] + siz[y] - i - j][siz[x] - i] % P * (f[y][siz[y]] - f[y][j] + P) % P);
        } else {
            for (int i = 1; i <= siz[x]; ++i)
                for (int j = 1; j <= siz[y]; ++j)
                    add(f[x][i + j], g[i] * C[i + j - 1][j] % P * C[siz[x] + siz[y] - i - j][siz[x] - i] % P * f[y][j] % P);
        }
        siz[x] += siz[y];
    }
    for (int i = 1; i <= siz[x]; ++i) f[x][i] = (f[x][i] + f[x][i - 1]) % P;
}

void solve(void) {
    scanf("%d", &n); memset(f, 0, sizeof(f)); 
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = 1; i < n; ++i) {
        int x, y; char c; scanf("%d %c %d", &x, &c, &y); ++x; ++y;
        addedge(x, y, c == '<'); // x -> y, y <- x
    }
    dfs(1, 0);
    printf("%d\n", f[1][n]);
}

int main(void) {
    for (int i = 0; i <= 1000; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
    int T; scanf("%d", &T);
    while (T--) solve();   
    return 0;
}

[CF1626E] Black and White Tree

Portal.

一个点能达到一个黑点，要么它自己是黑点，要么它的儿子是黑点，要么它儿子能到黑点且它儿子的子树中有至少两个黑点（这样如果儿子走黑点时第一步选择一号黑点，那么当前节点就可以选择二号黑点走到儿子）。于是换根 DP 拍上去即可。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int n, a[300005], f[300005], g[300005], sz[300005];
vector<int> G[300005];

void dfs(int x, int fa) {
    if (sz[x] = a[x]) f[x] = 1;
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); sz[x] += sz[y];
        if (a[y]) f[x] = 1; if (f[y] && sz[y] > 1) f[x] = 1; 
    }
}

void dfs2(int x, int fa) {
    if (a[fa]) g[x] = 1; g[x] |= f[x];
    for (int y : G[x]) if (y != fa) {
        if (g[x] && sz[1] - sz[y] > 1) g[y] = 1; 
        dfs2(y, x);
    }
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);    
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    dfs(1, 0); dfs2(1, 0);
    for (int i = 1; i <= n; ++i) printf("%d ", g[i]); putchar('\n');
    return 0;
}

状压 DP

不是很难。

[BJWC2018] 最长上升子序列

Portal.

设 f(i,j)f(i,j) 代表考虑长度为 ii 的序列，LIS DP 后的 ff 数组（取一遍前缀最大值）的差分状压后为 jj 的方案数。转移也不难。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int P = 998244353;

int poww(i64 a, int b) {
    int res = 1; a %= P;
    for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
    return res;
}
void add(int &x, int t) { x = (x + t) % P; }

int n;
int f[2][134217728];

int main(void) {
    scanf("%d", &n); 
    if (n == 25) return puts("102117126"), 0;
    if (n == 26) return puts("819818153"), 0;
    if (n == 27) return puts("273498600"), 0;
    if (n == 28) return puts("267588741"), 0;
    --n; f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 1 << i; ++j) f[i & 1][j] = 0;
        for (int j = 0; j < 1 << i - 1; ++j) {
            int t, pos = -1;
            for (int k = i - 1; k >= 0; --k) { // 插入到第 k 位
                t = (j >> k << k + 1) | (1 << k) | (j & (1 << k) - 1);
                if (j & 1 << k) pos = k;
                if (pos != -1) t ^= 1 << pos + 1; 
                add(f[i & 1][t], f[i - 1 & 1][j]);
            }
            add(f[i & 1][j << 1], f[i - 1 & 1][j]); // 插在第 0 个位置
        }
    }
    i64 fac = 1, ans = 0;
    for (int i = 0; i < 1 << n; ++i) ans = (ans + 1ll * f[n & 1][i] * (__builtin_popcount(i) + 1)) % P;
    for (int i = 1; i <= n + 1; ++i) fac = fac * i % P;
    ans = ans * poww(fac, P - 2) % P;
    printf("%d\n", ans);
    return 0;
}

[九省联考 2018] 一双木棋 chess

Portal.

发现合法的放棋子状态不是很多，因此可以把它们先搜出来，然后直接 DP。由于选手足够聪明，所以 DP 要倒序进行。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int B = 233, P = 998244353;

int n, m, tot, cnt[15];
int a[15][15], b[15][15];

int H(void) {
    int res = 0;
    for (int i = 1; i <= m; ++i) res = (1ll * res * B + cnt[i]) % P;
    return res;
}

int id[200005], rev[200005];
int val[200005], f[2][200005];
int s[200005][15];
map<int, int> h;

void dfs(int x) {
    if (x == m + 1) {
        h[H()] = ++tot;
        for (int i = 1; i <= m; ++i) {
            val[tot] += cnt[i];
            s[tot][i] = cnt[i];
        }
        return;
    }
    for (int i = 0; i <= cnt[x - 1]; ++i) cnt[x] = i, dfs(x + 1);
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &b[i][j]);
    cnt[0] = n; dfs(1);
    for (int i = 1; i <= tot; ++i) id[i] = i;    
    sort(id + 1, id + tot + 1, [](int x, int y) { return val[x] > val[y]; }); 

    for (int i = 1; i <= tot; ++i) rev[id[i]] = i; 
    memset(f[0], -0x3f, sizeof(f[0])); memset(f[1], 0x3f, sizeof(f[1]));
    
    // 1: 对手落子 0: 自己落子
    if ((n * m) & 1) f[1][1] = 0;
    else f[0][1] = 0;
    for (int i = 1; i < tot; ++i) {
        int x = id[i], k, o, hash;
        for (int p = 1; p <= m; ++p) {
            for (int q = 1; q <= m; ++q) {
                cnt[q] = s[x][q];
                if (q == p) o = cnt[q], --cnt[q];
            }
            if (h.find(hash = H()) == h.end()) continue;
            k = rev[h[hash]]; 

            if (val[x] & 1) f[0][k] = max(f[0][k], f[1][i] + a[o][p]); 
            else f[1][k] = min(f[1][k], f[0][i] - b[o][p]);
        }
    }
    printf("%d\n", f[0][tot]);
    return 0;
}

[PKUSC2018] 最大前缀和

Portal.

考虑最大前缀和的特点。如果一个数作为最大前缀和的末尾，那么它后面的序列单独拎出来，没有一个前缀非负。根据此 DP 即可。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353, N = 1 << 20; 

int n; 
int s[N], f[N], g[N]; 

int main(void) {
    scanf("%d", &n); 
    for (int i = 0; i < n; ++i) scanf("%d", &s[1 << i]), f[1 << i] = 1; 
    for (int i = 1; i < 1 << n; ++i) s[i] = s[i ^ (i & -i)] + s[i & -i]; 
    for (int i = g[0] = 1; i < 1 << n; ++i) 
        if (s[i] >= 0) {
            for (int j = 0; j < n; ++j)
                if (!(i >> j & 1)) f[1 << j | i] = (f[i] + f[1 << j | i]) % P; 
        } else {
            for (int j = 0; j < n; ++j)
                if (i >> j & 1) g[i] = (g[i] + g[i ^ (1 << j)]) % P; 
        }
    int ans = 0; 
    for (int i = 1; i < 1 << n; ++i) ans = (ans + 1ll * s[i] * f[i] % P * g[(1 << n) - 1 ^ i] % P) % P; 
    return printf("%d\n", (ans + P) % P), 0;
}

[省选联考 2021 A/B 卷] 滚榜

Portal.

显然是可以贪心的，贪心策略跟上一个滚出来的队伍有关。设 fS,i,jf_{S,i,j} 表示滚出来的队伍集合是 SS，上一个滚出来的是 ii，总共消耗的题目是 jj。转移很容易。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m; 
int a[15], t = 14, cnt[1 << 13], p[1 << 13]; 
i64 f[1 << 13][13][505]; 

int main(void) {
    scanf("%d%d", &n, &m); a[n] = -1; t = n; 
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i); p[1 << i] = i; 
        if (a[i] > a[t]) t = i; 
    }
    for (int i = 0; i < n; ++i) {
        int tar = n * (a[t] - a[i] + (t < i)); 
        if (tar <= m) f[1 << i][i][tar] = 1; 
    }
    cnt[1] = 1; 
    for (int i = 2; i < 1 << n; ++i) cnt[i] = cnt[i >> 1] + (i & 1); 
    for (int i = 0; i < 1 << n; ++i) {
        for (int s = i; s; s -= (s & -s))
            for (int k = 0; k <= m; ++k) {
                int j = p[s & -s]; 
                for (int l = 0; l < n; ++l) if (!(i >> l & 1)) {
                    int tar = k + (n - cnt[i]) * max(0, a[j] - a[l] + (j < l)); 
                    if (tar <= m) f[1 << l | i][l][tar] += f[i][j][k]; 
                }
            }
    }
    i64 ans = 0; 
    for (int i = 0; i < n; ++i) for (int j = 0; j <= m; ++j) 
        ans += f[(1 << n) - 1][i][j]; 
    return printf("%lld\n", ans), 0;
}

计数 DP

实际上考的最多的是这玩意儿。

[SDOI2019] 移动金币

Portal.

发现这是一个阶梯博弈问题，将 n−mn-m 个石子划给 m+1m+1 个阶梯。

我们求先手必败的方案数，然后用总方案数减去。先手必败要让偶数编号的阶梯异或和为 00（地面为 11）。设 fi,jf_{i,j} 为考虑到最终异或和的第 ii 位，还剩 jj 个石子没有放的方案数。因为这一二进制位为 11 的个数为偶数才能保证异或和为 00，所以 fi,j=∑2∣kfi+1,j−2ik(m+12k)f_{i,j}=\sum_{2\mid k}f_{i+1,j-2^i k}\binom{\frac{m+1}{2}}{k}。剩余的石子可以插板放入奇数的阶梯位置。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 1000000009;  

i64 poww(i64 a, int b) { 
    int res = 1; 
    for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P; 
    return res; 
}

int n, m, ans; 
int f[20][150005];

i64 fac[150005]; 
i64 C(int n, int m) {
    return 1ll * fac[n] * poww(1ll * fac[m] * fac[n - m] % P, P - 2) % P; 
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % P; 
    int t = 1; 
    while ((1 << t) <= n) ++t; 
    f[t][n - m] = 1; 
    int even = (m + 1) / 2, odd = m + 1 - even; 
    for (int i = t - 1; i >= 0; --i)
        for (int j = 0; j <= n - m; ++j) {
            if (!f[i + 1][j]) continue; 
            for (int k = 0; k <= (m + 1) / 2 && k * (1 << i) <= j; k += 2)
                f[i][j - k * (1 << i)] = (f[i][j - k * (1 << i)] + f[i + 1][j] * C(even, k)) % P;
        }
    i64 ans = 0; 
    for (int i = 0; i <= n - m; ++i) ans = (ans + f[0][i] * C(i + odd - 1, i)) % P;
    printf("%lld\n", (C(n, m) - ans + P) % P);
    return 0;
}

数位 DP

实际上发现都是模板。有些会与字符串算法相结合。

【SWTR-02】Magical Gates

Portal.

对 nn 的二进制位从高到低枚举，并令所有枚举到的 11 位都填 11。如果当前位置是 11，也可以这一位不填 11，后面的位随便，这样就可以计算出表示二进制下有 ii 个 11 的数的个数的 f(i)f(i)，就可以直接统计。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
int P;

int poww(i64 a, int b) {
    int res = 1; for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
    return res;
}

int C[3505][3505], CC[3505][3505];
string l, r;
int p[1005], a[3505], tot;

void change(string &s, bool f) {
    memset(a, 0, sizeof(a));
    int len = s.length() - 1; tot = 0;
    for (int i = len; i >= 0; --i) p[i] = s[len - i] - '0';
    if (f) {
        --p[0];
        for (int pos = 0; p[pos] < 0; ++pos) --p[pos + 1], p[pos] += 10;
        if (!p[len]) --len;
    }
    while (len >= 0) {
        int res = 0;
        for (int i = len; i >= 0; --i) {
            res = res * 10 + p[i];
            p[i] = res / 2; res %= 2;
        }
        a[tot++] = res;
        if (!p[len]) --len;
    }
    --tot;
}

i64 f[3505], g[3505];

void solve(void) {
    memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
    cin >> l >> r;
    change(r, 0); int t = 0;
    for (int i = tot; i >= 0; --i) if (a[i]) {
        for (int j = 1; j <= i; ++j) { // 这一位不填 1，后面的随便填
            f[j + t] = (f[j + t] + C[i][j]) % P;
            g[j + t] = (g[j + t] + CC[i][j]) % (P - 1);
        }
        ++f[++t]; ++g[t]; // 这一位填 1
    }
    change(l, 1); t = 0;
    for (int i = tot; i >= 0; --i) if (a[i]) {
        for (int j = 1; j <= i; ++j) {
            f[j + t] = (f[j + t] - C[i][j]) % P;
            g[j + t] = (g[j + t] - CC[i][j]) % (P - 1);
        }
        --f[++t]; --g[t];
    }

    i64 ans1 = 0, ans2 = 1;
    for (int i = 1; i <= 3400; ++i) {
        f[i] = (f[i] % P + P) % P; g[i] = (g[i] % (P - 1) + P - 1) % (P - 1);
        ans1 = (ans1 + i * f[i]) % P; ans2 = ans2 * poww(i, g[i]) % P;
    }
    printf("%lld %lld\n", ans1, ans2);
}

int main(void) {
    int T, n; scanf("%d%d%d", &T, &P, &n);
    for (int i = 0; i <= 3500; ++i)
        for (int j = C[i][0] = CC[i][0] = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
            CC[i][j] = (CC[i - 1][j] + CC[i - 1][j - 1]) % (P - 1);
        }
    while (T--) solve();
    return 0;
}

[BalticOI 2013 Day1] Palindrome-Free Numbers

Portal.

如果是非回文，那么只需要不出现长度为 22 或 33 的回文串即可（因为回文串两头缩减之后还是回文串），因此只需要记录前两位。

查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int num[20], len; 
i64 f[20][11][11][2][2]; 

i64 dp(int p, int p1, int p2, bool lim, bool st) {
    if (p == 0) return 1; 
    if (f[p][p1][p2][lim][st] != -1) return f[p][p1][p2][lim][st]; 
    int mx = lim ? num[p] : 9; i64 res = 0;
    for (int i = 0; i <= mx; ++i) if (i != p2 && i != p1) {
        if (st && i == 0) res += dp(p - 1, 10, 10, lim && i == mx, 1); 
        else res += dp(p - 1, i, p1, lim && i == mx, 0); 
    }
    return f[p][p1][p2][lim][st] = res; 
}

i64 calc(i64 n) {
    memset(f, 0xff, sizeof(f)); len = 0; 
    while (n) num[++len] = n % 10, n /= 10;
    return dp(len, 10, 10, 1, 1); 
}

int main(void) {
    i64 l, r; cin >> l >> r; 
    cout << calc(r) - calc(l - 1) << "\n";    
    return 0;
}

DP 套 DP

部分题目相当麻烦。

[SDOI/SXOI2022] 小 N 的独立集

Portal.

给定一棵 n(n≤1000)n(n\le 1000) 个节点的树，每个节点的权值可以随意在 1∼k(k≤5)1\sim k(k\le 5) 中给定，问答案为 1∼nk1\sim nk 的最大权独立集问题的树各有多少棵。

最大独立集问题非常经典，设 fx,0/1f_{x,0/1} 代表节点 xx 的子树中是否选择 xx 的最大答案。把 ff 的值压进去作为 DP 的状态，设 gx,v0,v1g_{x,v0,v1} 代表 xx 的子树中 fx,0=v0,fx,1=v1f_{x,0}=v0,f_{x,1}=v1 的方案数，但是这样状态数炸了！

想办法简化状态数。设 fx,0/1f_{x,0/1} 代表是否强制不选时的最大答案，但这样发现 0≤fx,0−fx,1≤valx0\le f_{x,0}-f_{x,1}\le val_{x}，这样我们就可以不用保存 fx,0f_{x,0}，而是只记录它们的差值 dd，这样状态就可以记录为 gx,v,dg_{x,v,d} 代表 fx,0f_{x,0} 的值为 v+dv+d，fx,1f_{x,1} 的值为 vv。

初始 gx,0,i=1(1≤i≤k)g_{x,0,i}=1(1\le i\le k)，外层 DP 的转移是一个树形背包的形式。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007; 
void add(int &a, int b) { a += b; if (a >= P) a -= P; }

int n, k, siz[1005];
vector<int> G[1005]; 
int g[1005][5005][6], f[5005][6]; 

void dfs(int x, int fa) {
    siz[x] = 1; 
    for (int i = 1; i <= k; ++i) g[x][0][i] = 1; // 将自己设置为 1 ~ k 的方案数都为 1
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); memset(f, 0, sizeof(f)); 
        for (int i = 0; i <= k * siz[x]; ++i) // dp[x][1] = i
          for (int j = 0; j <= k; ++j) if (g[x][i][j]) // dp[x][0] = i + j
            for (int p = 0; p <= k * siz[y]; ++p) // dp[y][1] = p
              for (int q = 0; q <= k; ++q) if (g[y][p][q]) // dp[y][0] = p + q
                add(f[i + p + q][max(i + j + p, i + p + q) - (i + p + q)], 1ll * g[x][i][j] * g[y][p][q] % P); 
        memcpy(g[x], f, sizeof(f)); siz[x] += siz[y]; 
    }
}

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u);
    } dfs(1, 0);
    for (int i = 1; i <= n * k; ++i) {
        int ans = 0; 
        for (int j = 0; j <= min(i, k); ++j) add(ans, g[1][i - j][j]);
        printf("%d\n", ans); 
    }
    return 0;
}

插入法 DP

一种特殊的状态设计方法。

[CEOI2016] kangaroo

Portal.

相当于是构造一个排列，左右是 s,ts,t，任意元素满足它左右两个都比它大或都比它小。

常规方法并不好处理，考虑一种以插入为转移的 DP。设 fi,jf_{i,j} 代表考虑前 ii 个数，将序列划分成 jj 段的方案数。

一个数可以用来新增一个段，也可以用来合并段。如果它是 s,ts,t 那么只能将它放到首尾。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007; 

int n, s, t; 
int f[2005][2005]; 

int main(void) {
    scanf("%d%d%d", &n, &s, &t); f[1][1] = 1; 
    for (int i = 2; i <= n; ++i)
        if (i != s && i != t) {
            for (int j = 1; j <= i; ++j) { 
                int c = (i > s) + (i > t);  
                f[i][j] = (1ll * j * f[i - 1][j + 1] + 1ll * (j - c) * f[i - 1][j - 1]) % P; 
            } 
        } else {
            for (int j = 1; j <= i; ++j)
                f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % P;; 
        }
    printf("%d\n", f[n][1]); 
    return 0; 
}

[CF1515E] Phoenix and Computers

Portal.

  • 新增一段，方案数是 fi−1,j−1×jf_{i-1,j-1}\times j；
  • 与原来段相连，可以贴着或者隔一个放，段的左右位置都可以；
  • 合并段，中间有两个空或三个空可以合并。
查看代码 
#include <bits/stdc++.h>
using namespace std;

int n, P; 
int f[405][405]; 
inline void add(int &x, int t) { x += t; if (x >= P) x -= P; }

int main(void) {
    scanf("%d%d", &n, &P); f[1][1] = 1; 
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= i; ++j) {
            add(f[i][j], 1ll * f[i - 1][j - 1] * j % P); 
            add(f[i][j], 2ll * f[i - 1][j] * j % P); // 贴着
            add(f[i][j], 2ll * f[i - 2][j] * j % P); // 隔着一个
            add(f[i][j], 2ll * f[i - 2][j + 1] * j % P); // 两个中的任意一个
            if (i >= 3) add(f[i][j], 1ll * f[i - 3][j + 1] * j % P); // 三个中间的那个
        }
    printf("%d\n", f[n][1]); 
    return 0; 
}

[AT DP] 文字列

Portal.

设 fi,jf_{i,j} 代表考虑前 ii 种字符，有 jj 组相邻的字符的方案数。

转移时枚举 jj，当前字母分成的段数 kk，打散原来的 ll 段字母。然后简单组合一下即可。

查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007, N = 262; 
inline void add(int &x, int t) { x = (x + t) % P; }

int a[30], n, m; 
int C[265][265], f[30][265]; 

int main(void) {
    for (int i = 0; i <= N; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; 
    for (int i = 0; i < 26; ++i) cin >> a[i]; 
    f[0][max(0, a[0] - 1)] = 1; n = a[0]; 
    for (int i = 1; i < 26; ++i) {
        if (!a[i]) continue; ++m; 
        for (int j = 0; j <= n; ++j) if (f[m - 1][j])
            for (int k = 1; k <= a[i]; ++k)
                for (int l = 0; l <= min(j, k); ++l) {
                    int now = j - l + a[i] - k;
                    add(f[m][now], 1ll * f[m - 1][j] * C[a[i] - 1][k - 1] % P * C[j][l] % P * C[n + 1 - j][k - l] % P); 
                    // 插板出分段数，选择 l 段打散，剩下随意插入
                }
        n += a[i];  
    }
    printf("%d\n", f[m][0]); 
    return 0;
}

综合应用

非常好玩！

[ABC262G] LIS with Stack

Portal.

感觉像个 DP。考虑一个数要被放置，它需要在它顶上那个元素弹栈之后才可以被放入序列。如果要有贡献，需要限制它前面的最大值和它后面的最小值。很有合并的感觉！考虑区间 DP。设 f(i,j,mn,mx)f(i,j,mn,mx) 代表考虑 [i,j][i,j] 的数，放的最大值是 mxmx，最小值是 mnmn 的最大答案。可以选择删除 ii，不删除时枚举它顶上的元素 kk（也可以是它自己），将区间拆分成两段并限制最值。

查看代码 
#include <bits/stdc++.h>
using namespace std;

int n; 
int a[55], f[55][55][55][55]; 

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i); 
        for (int l = 1; l <= a[i]; ++l)
            for (int r = a[i]; r <= 50; ++r)
                f[i][i][l][r] = 1; 
    }
    for (int len = 2; len <= n; ++len)    
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1; 
            for (int mn = 1; mn <= 50; ++mn)
                for (int mx = mn; mx <= 50; ++mx) {
                    int &dp = f[i][j][mn][mx]; 
                    dp = f[i + 1][j][mn][mx]; 
                    if (mn <= a[i] && a[i] <= mx) {
                        for (int k = i; k <= j; ++k)
                            dp = max(dp, f[i + 1][k][mn][a[i]] + f[k + 1][j][a[i]][mx] + 1); 
                    }
                }
        }
    printf("%d\n", f[1][n][1][50]); 
    return 0;     
}

[CF115D] Unambiguous Arithmetic Expression

Portal.

先将表达式标准化。设 fi,j,0/1f_{i,j,0/1} 代表考虑到第 ii 位，有 jj 个左括号没有匹配，最后一个括号是左括号或右括号。转移时采用刷表法：

  • fi,j,1f_{i,j,1} 可以转移到以下位置：
    • fi+1,j+1,0f_{i+1,j+1,0}，只需要新建一个左括号即可，不管当前位置是什么这样都是合法的，由于括号内不能是空的因此 i+1i+1；
    • fi,j−1,1f_{i,j-1,1}，用一个右括号匹配；
  • fi,j,0f_{i,j,0} 可以转移：
    • 如果当前是个乘除号，那么转移不了；
    • 是个加减号，可以选择在这个符号右边套一个左括号；
    • 是数字，可以考虑用括号将数字包起来，或者跟一个左括号匹配。
查看代码 
#include <bits/stdc++.h>
using namespace std;
const int P = 1000003; 
const int N = 2005; 
inline void add(int &x, int t) { x += t; if (x >= P) x -= P; }

int n, m, f[2010][2010][2]; 
char a[2010], s[2010]; 

int main(void) {
    scanf("%s", a + 1); n = strlen(a + 1); 
    for (int i = 1; i <= n; ) {
        if (a[i] == '+' || a[i] == '-') ++i, s[++m] = '+'; 
        else if (a[i] == '*' || a[i] == '/') ++i, s[++m] = '*'; 
        else {
            s[++m] = '0'; 
            while (i <= n && isdigit(a[i])) ++i; 
        }
    }
    if (m == 1 && s[1] == '0') return puts("1"), 0;
    f[1][0][0] = 1; 
    for (int i = 1; i <= m + 1; ++i) {
        for (int j = N - 1; j >= 0; --j) if (f[i][j][1]) {
            add(f[i + 1][j + 1][0], f[i][j][1]);  
            if (j) add(f[i][j - 1][1], f[i][j][1]); 
        }
        for (int j = 0; j < N; ++j) if (f[i][j][0]) {
            if (s[i] == '+') add(f[i + 1][j + 1][0], f[i][j][0]); 
            if (s[i] == '0') add(f[i + 2][j + 1][0], f[i][j][0]); 
            if (s[i] == '0' && j) add(f[i + 1][j - 1][1], f[i][j][0]); 
        }
    }
    printf("%d\n", f[m + 1][0][1]); 
    return 0; 
}

[IOI2022] 鲶鱼塘

Portal.

画一画就发现长堤一定是单峰的。那么设 dpi,0/1dp_{i,0/1} 代表第 ii 条鲶鱼通过左边 / 右边的限制可选时的最大重量，fif_{i} 代表现在长堤增的最大重量，gig_{i} 代表递减。可以从当前一列转移，也可以枚举这一列的鲇鱼然后下面的全部填上长堤。

查看代码 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;
typedef long long i64; 

int x[300005], y[300005], w[300005]; 
i64 dp[300005][2], f[300005], g[300005]; // [][0] 代表上升
// f g 分别代表现在是增、减的最优值
vector<int> v[300005]; // i 位置上的垒球
i64 max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < m; ++i) {
        x[i + 1] = X[i] + 1, y[i + 1] = Y[i] + 1, w[i + 1] = W[i];
        v[X[i] + 1].emplace_back(i + 1);
    }

    for (int i = 1; i <= n; ++i) {
        sort(v[i].begin(), v[i].end(), [&](int a, int b) { return y[a] < y[b]; });
        f[i] = g[i] = max(f[i - 1], g[i - 1]);

        int l1 = v[i - 1].size(), l2 = v[i].size(), c = l1; 
        i64 mx = i >= 2 ? max(f[i - 2], g[i - 2]) : 0;

        if (i != 1) {
            for (int j = l2 - 1; j >= 0; --j) { // 从 y 坐标高开始
                if (j < l2 - 1) dp[v[i][j]][0] = dp[v[i][j + 1]][0] + w[v[i][j]]; // 同一列
                while (c && y[v[i - 1][c - 1]] > y[v[i][j]])
                    mx = max(mx, dp[v[i - 1][--c]][0]);
                dp[v[i][j]][0] = max(dp[v[i][j]][0], mx + w[v[i][j]]); 
                f[i] = max(f[i], dp[v[i][j]][0]);
            }
        }

        c = 0; mx = f[i - 1];
        if (i != n) {
            for (int j = 0; j < l2; ++j) {
                if (j) dp[v[i][j]][1] = dp[v[i][j - 1]][1] + w[v[i][j]];
                while (c < l1 && y[v[i - 1][c]] < y[v[i][j]])
                    mx = max(mx, dp[v[i - 1][c++]][1]);
                dp[v[i][j]][1] = max(dp[v[i][j]][1], mx + w[v[i][j]]); 
                g[i] = max(g[i], dp[v[i][j]][1]);
            }
        }
    }
    i64 ans = 0;
    for (int i = 1; i <= m; ++i) ans = max({ans, dp[i][0], dp[i][1]});
    return ans;
}
动态规划的状态设计
https://james1badcreeper.github.io/bb10c5df/
本文作者
james1BadCreeper
发布于
2023年1月9日
更新于
2023年4月1日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

发布于 2023年1月9日
算法竞赛学习笔记动态规划

动态规划

评论

若无法加载，请尝试刷新，欢迎讨论、交流和提出意见，支持 Markdown 与 LaTeX 语法（公式与文字间必须有空格）！