两年前的种的向日葵的萌芽，可惜还没成长就死了。
讲解了数位、状压、期望 dp。
一、数位 DP
数位 DP 是通过 DP 的方式来计算符合某种条件的数的个数，多用于计算大整数以及数码相关的问题。下面通过一道题来体会这种 DP 的过程与内涵。
题意：给出 $l$ 与 $r$，求 $[l,r]$ 中满足相邻两个数字之差至少为 $2$ 的正整数的个数，$l,r\le 2\times10^9$。
分析：注意到数据范围很大，故无法直接枚举求解。于是考虑动态规划。
显然区间中满足条件的数个数满足单调关系，且可以进行前缀和操作。我们设 $ans(r)$ 表示 $[1,r]$ 中满足条件数的个数。则答案即为 $ans(r)-ans(l-1)$，此时我们只需求解 $[1,n]$ 的答案，即可得题目之所求。
由于动态规划的阶段性，我们可以暂时确定求解答案的顺序。数位 DP 中，我们通常将一个大整数看作一个由 $[0,9]$ 构成的整数序列，自高位至地位一位一位地 DP。
于是状态设计便呼之欲出。设 $f(i,j)$ 表示当前已经填好最高的前 $i$ 位，且第 $i$ 位为 $j$ 的满足条件的数的个数。但倘若只限定如上条件，显然需要在原有基础上继续增加条件，于是状态即为 $f(i,j,lim,zero)$，后两维状态表示为：
$lim=1$： 已经填好的前 $i$ 位等于上界的前 $i$ 位。$lim=0$：已经填好的前 $i$ 位小于上界的前 $i$ 位。
$zero=1$：已经填好的前 $i$ 位均为 $0$，即含前导零。$zero=0$：已经填好的前 $i$ 位均为 $0$，即不含前导零。
第三维状态的设计是显然的，而第四维状态对于前导零的认识，我们不妨举个例子：前 $i-1$ 位均为 $0$，而第 $i$ 位欲填 $1$，若未进行前导零的限制，则会判断第 $i$ 位与第 $i-1$ 位之差小于 $2$，将这种情况就不会被统计到最终答案，故需加上这一维度条件的限制。
我们将这种形式化的状态代入到这道题中，于是有以下状态设计：
$f(i,j,lim,zero)$：从高到低第 $i$ 位为 $j$，前 $i$ 位满足任意相邻两位数字之差至少为 $2$，且不超过上界。满足前 $i$ 位均等/小于上界前 $i$ 位，有/无前导零的方案数。
$ans(k)$ 即为 $\sum\limits_{i=0}^9[f(len,i,0,0)+f(len,i,1,0)]$。
其中 $len$ 指 $k$ 的位数。
而初始状态，即为：$f(0,0,1,1)=1$
如何进行 DP？
不妨设当前值已知，用当前值更新所有可达点即可，即为刷表法 。
具体来说，我们每次枚举一个已知状态，再枚举下一位要填的数字，判断是否可以满足条件，若满足，则用当前状态去更新下一位即可。
核心代码如下：
Code
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
int ans (int K) {
memset (f, 0 , sizeof f);
memset (num, 0 , sizeof num);
len = 0 ;
while (K) num[++ len] = K % 10 , K /= 10 ;
f[0 ][0 ][1 ][1 ] = 1 ;
reverse (num + 1 , num + len + 1 );
for (int i = 0 ; i < len; i ++ ) {
for (int j = 0 ; j <= 9 ; j ++ ) {
for (int lim = 0 ; lim < 2 ; lim ++ ) {
for (int zero = 0 ; zero < 2 ; zero ++ ) {
for (int k = 0 ; k <= 9 ; k ++ ) {
if (! zero && abs (k - j) < 2 ) continue ;
if (lim && k > num[i + 1 ]) break ;
f[i + 1 ][k][lim && num[i + 1 ] == k][zero && ! k] += f[i][j][lim][zero];
}
}
}
}
}
int ret = 0 ;
for (int i = 0 ; i <= 9 ; i ++ )
ret += f[len][i][0 ][0 ] + f[len][i][1 ][0 ];
return ret;
}
最后所求即为 $ans(r)-ans(l-1)$。
给出十一位数 $l,r$，求 $[l,r]$ 中满足以下条件的数的个数：
数字中至少包含 $3$ 个相邻的连续数字。
号码中不可同时出现 $8$ 和 $4$。
分析：显然可以套用数位 DP 的常用状态设计，但亦需考虑如何表示第一个条件。
设计状态为 $f(i,j,Same,_8,_4,lim)$，上文出现过的维度同前，下面解释新增三维度、删去前导零维度之因：
$Same$：以 $i$ 结尾的连续串长度。
$_8$：已填数中是否出现 $8$。
$_4$：已填数中是否出现 $4$。
对于前导零维度，由于所给的 $l$ $r$ 均为十一位数，故在答案统计时会删去具有前导零的数的重复部分。不过当 $l$ 达到最小值 $10^{10}$ 时，$l-1$ 会变成十位数，导致答案出错。我们只需强制使 $len=11$ 即可。
特别的，为了状态设计无后效性，若当前状态 $Same$ 已经达到 $3$，我们认为其所可更新的所有状态的 $Same$ 均为 $3$。
核心代码如下：
Code
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
ll work (ll x) {
memset (f, 0 , sizeof f);
memset (num, 0 , sizeof num);
len = 0 ;
while (x) num[++ len] = x % 10 , x /= 10 ; len = 11 ;
f[0 ][0 ][1 ][1 ][0 ][0 ] = 1 ; reverse (num + 1 , num + len + 1 );
for (int i = 0 ; i < len; i ++ ) {
for (int j = 0 ; j <= 9 ; j ++ ) {
for (int Same = 1 ; Same <= 3 ; Same ++ ) {
for (int lim = 0 ; lim < 2 ; lim ++ )
for (int k = 0 ; k <= 9 ; k ++ ) {
for (int _8 = 0 ; _8 < 2 ; _8 ++ )
for (int _4 = 0 ; _4 < 2 ; _4 ++ ) {
if (_4 && _8) continue ;
if (_4 && k == 8 || _8 && k == 4 ) continue ;
if (lim && num[i + 1 ] < k) continue ;
if (Same == 3 )
f[i+ 1 ][k][Same][lim && num[i+ 1 ] == k][_8 || k== 8 ][_4 || k== 4 ] +=
f[i][j][Same][lim][_8][_4];
else
f[i+ 1 ][k][j== k ? Same+ 1 : 1 ][lim && num[i+ 1 ] == k][_8 || k== 8 ][_4 || k== 4 ] +=
f[i][j][Same][lim][_8][_4];
}
}
}
}
}
ll ret = 0 ;
for (int i = 0 ; i <= 9 ; i ++ )
ret += f[len][i][3 ][0 ][0 ][0 ] + f[len][i][3 ][0 ][0 ][1 ] + f[len][i][3 ][0 ][1 ][0 ] +
f[len][i][3 ][1 ][0 ][0 ] + f[len][i][3 ][1 ][0 ][1 ] + f[len][i][3 ][1 ][1 ][0 ];
return ret;
}
二、状态压缩 DP
状态压缩，顾名思义，就是把一串复杂冗余的状态压缩成一个简洁易于表示的状态，数据范围通常较小。常见的是二进制压缩，如令 $S$ 的二进制表示中第 $i$ 位为 有/无使用第 $i$ 个物品，即设计状态中含有集合。状态转移时结合一些位运算技巧即可。
题意：给出 $n$ 个物品，体积为 $w _ 1, w _ 2, \cdots, w _ n$，现把其分成若干组，要求每组总体积小于等于 $W$，问最小分组数量。$n\le 18$
分析：我们设 $f(S)$ 表示集合 $S$ 中所有物品已经分好组的最小分组数。若当前集合为 $S$，每次枚举其子集 $T$，若 $S\oplus T$ 中所有物品体积之和小于 $W$，则用 $f(T)+1$ 来更新 $f(S)$。
复杂度分析：考虑 $[1,n]$ 中每个物品。每次枚举的子集要么包含 $i$，要么不包含 $i$。接着枚举的子集之子集，要么包含 $i$，要么不包含 $i$。又由于第二个集合为第一个集合的子集，故每个数有三个状态：属于两个集合，属于第一个集合，不在集合中。时间复杂度为 $\mathcal O(3^n)$。
核心代码如下。
Code
1
2
3
4
5
for (int i = 1 ; i < 1 << n; i ++ ) {
f[i] = n + 1 ;
for (int j = i; j; -- j &= i)
if (sum[j] <= W) f[i] = min (f[i], f[i ^ j] + 1 );
}
题意：在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
分析：这道状压 DP 也许与上一题有些许不同，但本质如一。设计 $f(i,S,k)$ 表示已经放完前 $i$ 行，放了一共 $k$ 个国王，第 $i$ 行的放了国王王的集合为 $S$ 的方案总数。
预处理所有一行上满足条件的集合，以优化 DP 时的时间复杂度。
依次枚举第 $i$ 行状态 $S$，上一行状态 $T$，若满足题设条件，则用 $f(i-1,T,k)$ 更新当前的 $f(i,S,\mathrm {card}(S)+k)$。
Code
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
#include <cstdio>
#include <vector>
#define LL long long
using namespace std;
const int MAXN = 10 ;
LL ans;
int n, k;
LL f[MAXN][1 << MAXN][MAXN* MAXN];
vector < int > op;
void init () {
for (int state = 0 ; state < 1 << n; state ++ ) {
if (state << 1 & state || state >> 1 & state)
continue ;
op.push_back (state);
}
f[0 ][0 ][0 ] = 1 ;
}
void dp () {
for (int i = 1 ; i <= n; i++ ) {
for (auto newS : op) {
for (auto sourS : op) {
if (newS & sourS ||
newS << 1 & sourS ||
newS >> 1 & sourS
) continue ;
int count = 0 , tmp = newS;
while (tmp) {
++ count;
tmp &= (tmp - 1 );
}
for (int j = 0 ; j <= k - count; j++ )
f[i][newS][j + count] += f[i - 1 ][sourS][j];
}
}
}
}
void calc () {
for (auto S : op)
ans += f[n][S][k];
}
int main (void ) {
scanf ("%d %d" , & n, & k);
init ();
dp ();
calc ();
printf ("%lld \n " , ans);
return 0 ;
}
三、概率/期望 DP
相关的概念已经在 概率与期望
中讲到，故直接看例题。
题意：$n$ 个人从第 $1$ 个开始轮流朝自己开枪，射中的概率均为 $P_0$，剩下的最后一个人为胜利者。求第 $k$ 个人胜利的概率。特别的，若 $P_0=0$，则认为第一个人胜利。
分析：设 $P(i,j)$ 指剩余 $i$ 人，第 $j$ 人获胜的概率。考虑从第一个人开始，若射中，则剩下 $i-1$ 人，原先的第 $j$ 个人变为 $j-1$，对于 $P(i,j)$ 的贡献为 $P_0\times P(i-1,j-1)$；若没中，则仍有 $i$ 人，由于游戏继续，故当前的第 $j$ 人仍变成第 $j-1$ 人，做出贡献为 $(1-P_0)\times P(i,j-1)$。考虑第 $1$ 个人胜利的情况。此时其为第一个开枪者，绝对不中，而轮到下一个人后，其便成为第 $i$ 个人，故概率为 $(1-P_0)\times P(i,i)$。综上，如下：
$$P(i,j)=\begin{cases}P_0\times P(i-1,j-1)+(1-P_0)\times P(i,j-1), & j\ge 2 \ (1-P_0)\times P(i,i) & j=1\end{cases}$$
呈环形结构，考虑变形。设 $P(i,1)=x$，则情况 1 2 联立必可构造出形如 $ax+c=0$ 的方程，解之即可。
由于本题空间较小，故需滚动数组优化。
Luogu P5249 Code
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
#include <iostream>
using namespace std;
const int MAXN = 1e4 + 10 ;
int n, k;
long double P0;
long double P[2 ][MAXN];
int main (void ) {
scanf ("%Lf%d%d" , & P0, & n, & k); int N = 1 ;
if (P0 < 1e-8 ) return puts ("0" ) & 0 ;
P[0 ][1 ] = 1 ;
for (int i = 2 ; i <= n; i ++ ) {
double a = 1 , b = 0 ;
for (int j = 2 ; j <= i; j ++ ) a = a * (1 - P0), b = b * (1 - P0) + P[N ^ 1 ][j - 1 ] * P0;
P[N][1 ] = (1 - P0) * b / (1 - (1 - P0) * a);
for (int j = 2 ; j <= i; j ++ ) P[N][j] = P[N][j - 1 ] * (1 - P0) + P[N ^ 1 ][j - 1 ] * P0;
N ^= 1 ;
}
printf ("%.10Lf \n " , P[N ^ 1 ][k]);
return 0 ;
}
