状态设计

动态规划是 OI 最重要的部分之一。从学习与做题的角度来说，主要分为设计状态与优化两部分。其中前者更多的是做题和总结方法与套路，甚至需要一定的灵感；而后者相对吃经验。

值得注意的是，很多题目都要求我们在设计算法以前先将题目进行一定的转化，从而将一个不熟悉的模型转化为我们更容易把握的模型。这一点在动态规划的题目中体现的尤为明显。

在阅读本文之前，你应该对动态规划有基本的了解。

线性 DP

在线性结构上枚举每一维度进行转移的 DP。

直接做怎么做？设 $f_{i,j,k}$ 表示前 $i$ 个数，当前前缀和为 $j$，最大前缀和为 $k$，然后枚举填什么刷表转移对于每个状态是 $O(1)$ 的，虽然能做，但是状态数炸了。

需要合并无效状态。同时记录前缀和和最大前缀和有些冗余，从这里入手。考虑对于一段后缀，如果它本身的最大前缀和是 $0$，那么它不会对前面的贡献产生影响，这时可以直接确定排除掉这段后缀的前缀的答案，也就是题目所求。

设 $f_{i,j}$ 代表考虑前 $i$ 个数，且满足 $[i+1,n]$ 的最大前缀和为 $j$ 的期望答案，答案是 $f_{i,0}$。那么转移：

• 如果 $j>0$，可以以 $p_i$ 的系数（第 $i+1$ 位填 $1$）转移到 $f_{i+1,j-1}$，$1-p_i$ 的系数（第 $i+1$ 位填 $-1$）转移到 $f_{i+1,j+1}$。
• 如果 $j=0$，那么第 $i+1$ 位一定是 $-1$，此时可以转移到 $f_{i+1,0}$ 和 $f_{i+1,1}$。

代码。

背包

背包的变种很多，且都比较简单。基本模型：01 背包、完全背包、多重背包、分组背包、方案数背包的撤回（将转移的东西减去即可）。

区间 DP

图上 DP

状压 DP 与轮廓线 DP

动态 DP

其它 DP

一些杂项内容

插入法

数位 DP

一般的数位 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

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

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

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

例题

刷基础 1

只有 NOIP 难度。

[CSP-S 2024] 染色

Portal.

设 $f_i$ 代表考虑前 $i$ 位的答案。只有 $lst_{a_i}$ 可以与 $a_i$ 匹配，如果要匹配，中间一大段都要染成同一个颜色，计算这一段有多少贡献，从 $f_{lst_{a_i} + 1}$ 转移过来。

记录前缀某一段的贡献即可快速计算任意一段有多少贡献。代码。

刷提升 1

比较有趣。

[Ptz 2020 Summer Day4] Ternary String Counting

Portal.

$O(n^4)$ 直接 $f_{i,x,y,z}$ 记录每一个字符出现的位置，$O(n^3)$ 记录前两个不同字符的出现位置。都需要前缀和优化。

状态数还是过多了，我们需要寻找一个方式简化。先把转移写出来（对于状态 $f(i,j,k)$，表示当前考虑到第 $i$ 位，与这一位不同的数字上一次出现的位置分别位 $j,k$，并且 $j>k$）：

• $f(i+1,i,k)\stackrel{+}\leftarrow f(i,j,k)$；

• $f(i+1,i,j)\stackrel{+}\leftarrow f(i,j,k)$；

• $f(i+1,j,k)\stackrel{+}\leftarrow f(i,j,k)$。

再考虑题目中的限制，实际上就是限制了 dp 过程中 $j$ 和 $k$ 的取值范围：

1. $x=1$，则 $j<l$；
2. $x=2$，则 $j\ge l,k<l$；
3. $x=3$，则 $k\ge l$。

考虑优化，看上去第一维什么都不是！将转移分为 $i$​ 层，每一层的状态只能从上一层转移过来，第三个转移就是直接从上一层的对应点转移，第一二个转移是对上一层的一列和一行求和。

等价于，每次给出一个矩形，先把矩形外的值全部清零。然后还可以发现，一旦某个值被清零，那么这个值以后永远都是零。并且对于某一行来说，非零的值永远是一段连续区间，而且其位置是单调的。

双指针扫，不重复清零某个行即可。最终时间复杂度 $O(n^2+m)$。代码。