DP专题-专项训练：概率/期望 DP + 数位 DP
- 1. 前言
- 2. 题单
- 3. 概率/期望 DP
- P1850 [NOIP2016 提高组] 换教室
- P1654 OSU!
- CF518D Ilya and Escalator
- 总结
- 4. 数位 DP
- P2602 [ZJOI2010]数字计数
- P4124 [CQOI2016]手机号码
- P3286 [SCOI2014]方伯伯的商场之旅
- 总结
1. 前言
本文为 DP 算法总结&专题训练1，专门记载概率/期望 DP 和数位 DP 的经典练习题及其详解。
没有学过这两种 DP？
传送门：
接下来是题单。
2. 题单
概率/期望 DP：
- P1850 [NOIP2016 提高组] 换教室
- P1654 OSU!
- CF518D Ilya and Escalator
数位 DP：
- P2602 [ZJOI2010]数字计数
- P4124 [CQOI2016]手机号码
- P3286 [SCOI2014]方伯伯的商场之旅
上面的题目是有一定难度，但是又经典的题目。如果想做更多题目，可以到 luogu 上面查看，这份题单 非常好。
3. 概率/期望 DP
P1850 [NOIP2016 提高组] 换教室
这道题非常非常经典，可以说是概率/期望 DP 的一道好题目。
那么为什么我没有拿这道题做入门题讲解呢？主要是因为这道题的式子太长了，可能会吓退初学者。
首先无论换不换教室，我们都需要求出一些教室之间的最短路径，那么考虑到 \(v \leq 300\)，使用 \(\operatorname{Floyd}\) 算法（中文名：弗洛伊德算法）求最短路径显然是最方便的。什么？你没有学过？左转百度。。。。。。
那么开始设计 DP 的状态。
一个显然的思路就是设 \(f_{i,j}\) 表示当前正在决策第 \(i\) 堂课是否申请换教室，包括第 \(i\) 堂课在内已经申请了 \(j\) 堂课换教室所需要的期望最短路径。
于是这么做下去，你就会发现一个问题：写不出转移方程。
为什么？
因为我们在决策第 \(i\) 堂课的时候，不能只是考虑第 \(i\) 堂课换教室之后的位置，还需要考虑第 \(i-1\) 堂课有没有换教室，因为这联系到最短路的计算。
但是我们不知道第 \(i-1\) 堂课有没有换教室啊？于是我们需要添加一个状态。
那么设 \(f_{i,j,k}\) 表示当前正在决策第 \(i\) 堂课是否申请换教室，包括第 \(i\) 堂课在内已经申请了 \(j\) 堂课，且当前决定第 \(i\) 堂课申请换教室（\(k=1\)）/不申请换教室(\(k=0\)) 的期望最短路径。
注意：这里只是说申请换教室，而不是换教室成功。
那么接下来就可以设计状态转移方程了。
先看 \(f_{i,j,0}\)。
第一种情况：两堂课都不申请，为 \(f_{i-1,j,0}+dis_{c_{i-1},c_i}\)
第二种情况：上一堂课申请，此时需要考虑申请成功的概率 \(k_{i-1}\)，为 \(f_{i-1,j,1}+dis_{d_{i-1},c_i} \times k_{i-1}+dis_{c_{i-1},c_i} \times (1-k_{i-1})\)。
取最小值，那么有：
\[f_{i,j,0}=\min{(f_{i-1,j,0}+dis_{c_{i-1},c_i},f_{i-1,j,1}+dis_{d_{i-1},c_i} \times k_{i-1}+dis_{c_{i-1},c_i} \times (1-k_{i-1}))} \]接下来考虑 \(k=1\) 的情况。还是两种情况。
第一种情况，上一堂课不申请，那么需要考虑这一堂课的概率 \(k_i\)，为 \(f_{i-1,j-1,0}+dis_{c_{i-1},c_i} \times (1-k_i) + dis_{c_{i-1},d_i} \times k_i\)
第二种情况，两堂课都要申请，此时分申请成功与失败为四种情况，列表如下：
| 第 \(i\) 堂课 | 第 \(i-1\) 堂课 | 期望最短路径 |
|---|---|---|
| 成功 | 成功 | \(dis_{d_{i-1},d_i} \times k_i \times k_{i-1}\) |
| 成功 | 失败 | \(dis_{c_{i-1},d_i} \times k_i \times (1-k_{i-1})\) |
| 失败 | 成功 | \(dis_{d_{i-1},c_i} \times (1-k_i) \times k_{i-1}\) |
| 失败 | 失败 | \(dis_{c_{i-1},c_i} \times (1-k_i) \times (1-k_{i-1})\) |
求和，然后加上 \(f_{i-1,j-1,1}\)，就可以得到这种情况的结果了。
那么综合一下，就是：
\[f_{i,j,1}=\min{(f_{i-1,j-1,0}+dis_{c_{i-1},c_i} \times (1-k_i) + dis_{c_{i-1},d_i} \times k_i,f_{i-1,j-1,1}+dis_{d_{i-1},d_i} \times k_i \times k_{i-1}+dis_{c_{i-1},d_i} \times k_i \times (1-k_{i-1})+dis_{d_{i-1},c_i} \times (1-k_i) \times k_{i-1}+dis_{c_{i-1},c_i} \times (1-k_i) \times (1-k_{i-1}))} \]这式子是真的长
最后答案是：
\[\min_{i=0}^{t}{(f_{n,i,0},f_{n,i,1})} \]初始状态：\(f_{1,0,0}=f_{1,1,1}=0\)
于是就做完了。
几个注意点：
- 注意边界值的处理。
- 转移方程不能
抄写错。 - 小心卡精度。
作者的代码被卡精度了，WA了三个点，到目前为止没有调出来，因此请谨慎学习作者的代码。
总结：这道题实乃期望 DP 好题目，考察了各位面对一道图论上的序列性动态规划问题的解决思路，像解题时的加一维状态，列表求式子等等都是很常用的方法。
代码：
#include
#define Min(a, b) ((a < b) ? a : b)
using namespace std;
typedef double db;
typedef long long LL;
const int MAXN = 2e3 + 10, MAXV = 3e2 + 10;
int n, m, v, e, c[MAXN], d[MAXN], dis[MAXV][MAXV];
db k[MAXN], f[MAXN][MAXN][2], ans = 1e17 + 5;
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == -1) ? -sum : sum;
}
int main()
{
n = read(), m = read(), v = read(), e = read();
for (int i = 1; i <= n; ++i) c[i] = read();
for (int i = 1; i <= n; ++i) d[i] = read();
for (int i = 1; i <= n; ++i) scanf("%lf", &k[i]);
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= n; ++i) dis[i][i] = 0;
for (int i = 1; i <= e; ++i)
{
int x = read(), y = read(), z = read();
dis[x][y] = Min(dis[x][y], z);
dis[y][x] = Min(dis[y][x], z);
}
for (int k = 1; k <= v; ++k)
for (int i = 1; i <= v; ++i)
for (int j = 1; j <= v; ++j)
dis[i][j] = Min(dis[i][j], dis[i][k] + dis[k][j]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j)
f[i][j][0] = f[i][j][1] = 1e17 + 5;
f[1][0][0] = f[1][1][1] = 0;
for (int i = 2; i <= n; ++i)
{
f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
for (int j = 1; j <= min(i, m); ++j)
{
f[i][j][0] = Min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]));
if (j == 0) continue;
f[i][j][1] = Min(f[i - 1][j - 1][0] + dis[c[i - 1]][c[i]] * (1 - k[i]) + dis[c[i - 1]][d[i]] * k[i], f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i] * k[i - 1] + dis[c[i - 1]][d[i]] * k[i] * (1 - k[i - 1]) + dis[d[i - 1]][c[i]] * (1 - k[i]) * k[i - 1] + dis[c[i - 1]][c[i]] * (1 - k[i]) * (1 - k[i - 1]));
}
}
for (int i = 0; i <= m; ++i) ans = Min(ans, Min(f[n][i][0], f[n][i][1]));
printf ("%.2lf\n", ans);
return 0;
}
P1654 OSU!
方法一：
这道题的 DP 非常奇特，需要用到 差分 的思想。
我们先假设当前有连续 \(k\) 个 1，现在又添上一个 1，于是我们将贡献做差：
\((k+1)^3-k^3=(k+1)^2(k+1)-k^3=(k^2+2k+1)(k+1)-k^3=k^3+3k^2+3k+1-k^3=3k^2+3k+1\)
于是我们需要维护 \(3k^2+3k+1\) 的结果。
那么我们就需要维护 \(k^2\) 和 \(k\) 的结果。
接下来设 \(x1_i\) 表示处理到前 \(i\) 位 \(k\) 的期望，\(x2_i\) 表示处理到前 \(i\) 位 \(k^2\) 的期望。
那么转移的时候利用这两个式子：
\(x-1+1=x,(x-1)^2+2(x-1)+1=(x-1+1)^2=x^2\)
我们可以推出这样两个式子：
\(x1_i=(x1_{i-1}+1) \times p_i,x2_i=(x2_{i-1}+2 \times x1_{i-1}+1) \times p_i\)
那么由于答案的变化量为 \(3k^2+3k+1\)，记 \(ans_i\) 为前 \(i\) 位的期望贡献，有：
\(ans_i=ans_{i-1}+(3 \times x2_{i-1} + 3 \times x1_{i-1} + 1) \times p_i\)
于是就做完了。
总结：这道题是一道套路题，如果你不知道差分，那么这道题是真的很难做。但是你知道差分，那么这道题就会变得异常简单——只要你往这方面想。
但是如果考场上真的不知道差分怎么办？
记得差分的本质是什么吗？相邻两项相减，也就是找出 \(f_{i+1}-f_i\) 的关系。
于是方法二：列期望方程！
列期望方程可以说是最常见的一种解题思路了，这个方法无往不利，是期望 DP 的通法。
考虑 \(f_{i+1}\) 和 \(f_i\) 的关系，设此时在第 \(i\) 个位置出现连续 \(l\) 个 1 的概率是 \(p_l\)，第 \(i+1\) 位出现 1 的概率是 1，那么此时对答案多出来的贡献为 \(3l^2+3l+1\)。
考虑所有 \(l\) 的贡献，那么式子就长这样：
\(f_{i+1}=f_i+p \times \sum{p_l(3l^2+3l+1)}\)
然后我们就会发现只需要维护 \(l^2\) 和 \(l\) 的期望即可。
仿照上面的方法，我们会发现最后 \(l^2\) 的计算只需要计算 \(l\) 的期望，而 \(l\) 的期望好算啊！成功为 \(i-1\) 的期望 + 1 乘 \(p\)，失败就是 0。
这样，我们即使不知道差分，也可以愉快的通过此题了~
或许有的人会说了：差分这种套路比较难想啊，我怎么知道什么时候用差分呢？
还是使用期望方程来解释。
首先，在期望 DP 中，期望方程是用来联系 \(f_{i+1}\) 和 \(f_i\) 的关系的，在算法学习笔记里面我详细讲过。
而差分，就是当两者系数都是 1 而且移项之后两者正好做差，因此可以认为差分是期望方程的一种特殊情况。
所以其实不知道差分没有关系，照样可以列期望方程求解，只不过知道差分，就可以省略列出期望方程这一步。
以上只是个人观点，如有错误请读者指出。
代码：
#include
using namespace std;
typedef double db;
typedef long long LL;
const int MAXN = 1e5 + 10;
int n;
db p[MAXN], x1[MAXN], x2[MAXN], ans[MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == -1) ? -sum : sum;
}
int main()
{
n = read();
for (int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
for (int i = 1; i <= n; ++i)
{
x1[i] = (x1[i - 1] + 1) * p[i];
x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * p[i];
ans[i] = ans[i - 1] + (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * p[i];
}
printf("%.1lf", ans[n]);
return 0;
}
CF518D Ilya and Escalator
这道题的 DP 还是比较简单的。
设 \(f_{i,j}\) 表示第 \(i\) 个人在第 \(j\) 秒做出决策时的期望，那么：
- 走上电梯，那么为 \((f_{i-1,j-1}+1) \times p\)。
- 不走上电梯，那么为 \(f_{i,j-1} \times (1-p)\)
综上，我们有：
\[f_{i,j}=(f_{i-1,j-1}+1) \times p+f_{i,j-1} \times (1-p) \]然后递推即可。
代码：
#include
using namespace std;
typedef double db;
typedef long long LL;
const int MAXN = 2000 + 10;
int n, t;
double p, f[MAXN][MAXN];
int read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == -1) ? -sum : sum;
}
int main()
{
n = read(); scanf("%lf", &p); t = read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= t; ++j)
f[i][j] = f[i][j - 1] * (1 - p) + (f[i - 1][j - 1] + 1) * p;
printf("%.10lf\n", f[n][t]);
return 0;
}
总结
概率/期望 DP 的关键是确定 DP 状态，枚举各种可能性，推出各种可能性的状态转移方程，然后求和/取min/取max……，如果推不出 DP 方程可以列一下期望方程。而列期望方程这个方法非常好用，尤其是对付那些状态一维的问题。
4. 数位 DP
P2602 [ZJOI2010]数字计数
事先吐槽一句：为什么我数组越界了返回我 WA？查了好久的错……
开始正题。
这道题要我们求每个数码的出现次数，有两种解法：
第一种：边做边存每个数码出现的次数。
这个做法的原理还是比较好懂的，就是设状态 \(f[pos][sum][zero][limit][d]\) 表示在第 \(pos\) 位上统计后 \(cnt-pos\) 位数码 \(d\) 出现的次数，\(sum\) 表示前 \(pos\) 位数码 \(d\) 出现的次数为 \(sum\)，\(zero\) 和 \(limit\) 为前导零和最高位限制。
于是我们只需要设计这样的函数：LL dfs(int pos, int zero, int limit, int d)，数字位的统计使用一个全局变量数组（当然也可以采用参数为数组的形式），然后记忆化一下即可。
但是我个人感觉比较难写，于是第二种解法：暴力做 10 次，每一次确定一维数码的答案。
这个做法看起来就清爽，虽然时间复杂度会多一个 10 的常数，但是跑的还是特别快的，我们可以省略状态 \(d\)，但是 dfs 函数中不能省略。
此时的函数就会变为：LL dfs(int pos, int sum, int zero, int limit, int d)
代码？套板子。
代码：
#include
using namespace std;
typedef long long LL;
//const int MAXN = ;
LL l, r, f[15][15][2][2];
int cnt, a[15];
LL read()
{
LL sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == -1) ? -sum : sum;
}
LL dfs(int pos, int sum, int zero, int limit, int d)
{
if (pos == 0) return sum;
if (f[pos][sum][zero][limit] != -1) return f[pos][sum][zero][limit];
int t = limit ? a[pos] : 9; LL ans = 0;
for (int i = 0; i <= t; ++i)
{
if (i == 0 && zero) ans += dfs(pos - 1, sum, 1, i == a[pos] && limit, d);
else ans += dfs(pos - 1, sum + (i == d), 0, i == a[pos] && limit, d);
}
return f[pos][sum][zero][limit] = ans;
}
LL Get(LL k, int d)
{
memset(f, -1, sizeof(f)); cnt = 0;
for (; k; k /= 10) a[++cnt] = k % 10;
return dfs(cnt, 0, 1, 1, d);
}
int main()
{
l = read(), r = read();
for (int i = 0; i < 10; ++i)
printf("%lld ", Get(r, i) - Get(l - 1, i));
printf("\n"); return 0;
}
P4124 [CQOI2016]手机号码
这道题也是一道比较简单的数位 DP，虽然是紫题而且我调了 4 天
设计 dfs 函数：LL dfs(int pos, int pre1, int pre2, int tri, int num, int limit)
\(pos\) 是位置，\(pre1,pre2\) 表示前两位数字，\(tri\) 标记是否出现过连续 3 个数字，\(num\) 为 4 和 8 的标记，\(num=1\) 表示出现过 4，\(num=2\) 表示出现过 8。\(limit\) 是最高位限制。
细心的读者会发现了：为什么没有 \(zero\) 前导零标记呢？
这是因为，这道题题目上面明确规定必须是 11 位数，也就是 首位不能为 0。
然后就是套板子的事情。
当 \(i=pre1=pre2\) 时，\(tri=1\)，而出现 \(i=4 \& num=2\) 或者是 \(i=8 \& num=1\) 时不合法。
看样子很简单呀，那么为什么我错了呢？
理由很简单，因为 可以完全不包含 4 和 8。
一开始我的终止条件是：
if (pos == 0) return tri && num;
然后就是 WA，后来洛谷的 @keenlf 奆佬帮我指出了问题，在此表示感谢。
正确的写法应该是：
if (pos == 0) return tri;
代码：
#include
using namespace std;
typedef long long LL;
//const int MAXN = ;
int cnt, a[15];
LL l, r, f[15][15][15][2][3][2];
LL read()
{
LL sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == 1) ? sum : -sum;
}
LL dfs(int pos, int pre1, int pre2, int tri, int num, int limit)
{
if (pos == 0) return tri;
if (f[pos][pre1][pre2][tri][num][limit] != -1) return f[pos][pre1][pre2][tri][num][limit];
int t = limit ? a[pos] : 9; LL ans = 0;
for (int i = (pos == cnt) ? 1 : 0; i <= t; ++i)
{
if (i == 4 && num == 2) continue;
if (i == 8 && num == 1) continue;
if (pre1 == pre2 && pre2 == i) ans += dfs(pos - 1, pre2, i, 1, num ? num : ((i == 4) ? 1 : ((i == 8) ? 2 : 0)), i == a[pos] && limit);
else ans += dfs(pos - 1, pre2, i, tri, num ? num : ((i == 4) ? 1 : ((i == 8) ? 2 : 0)), i == a[pos] && limit);
}
return f[pos][pre1][pre2][tri][num][limit] = ans;
}
LL Get(LL k)
{
if (k < 1e10) return 0;
memset(f, -1, sizeof(f)); cnt = 0;
for (; k; k /= 10) a[++cnt] = k % 10;
return dfs(cnt, 0, 0, 0, 0, 1);
}
int main()
{
l = read(), r = read();
printf("%lld\n", Get(r) - Get(l - 1));
return 0;
}
P3286 [SCOI2014]方伯伯的商场之旅
这道题是道套路不太一般的数位 DP。
首先根据小学奥数知识我们可以得知：所有石子合并到最中间一定是最优的，然而这并没有什么用，也不知道什么在中间。
那么我们先思考一个问题：假设当前合并点为 \(tag\)，当我们将合并点更新为 \(tag+1\) 时，记 \(tag+1\) 时的答案为 \(ans_{tag+1}\)，第一位答案为 \(ans_1\)，那么：\(ans_{tag+1}-ans_1\) 是否具有单调性？
答案是：是。
为什么？我们将合并点不断右移的时候，显然更多的点会到左边，此时左边的石头会越来越多，导致每移动一格影响就会越来越大，因此有单调性。
那么我们就有了一种思路：首先先计算出合并到 1 号点的答案，然后贪心右移，答案能变小就变小。
于是这道题就做完了
到目前为止还没有做完，因为代码写不出来。
这道题的特别之处在于我们要写两个 dfs。
LL dfs1(int pos, int sum, int limit)
\(sum\) 表示已经算完位的贡献。LL dfs2(int pos, int sum, int tag, int limit)
\(tag\) 是新的合并点。
而在dfs2中，我们需要计算的是新的左边贡献减去右边贡献的差值，相当于一种前缀和的思想，如果算出来是正数，那么更新答案。
到这里就做完了。
代码注意：
- 随时清空 \(f\) 数组。
- 注意数位上界是 \(k-1\)！
代码：
#include
#define Max(a, b) ((a > b) ? a : b)
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;
LL l, r, f[70][MAXN];
int k, cnt, a[70];
LL read()
{
LL sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return (fh == 1) ? sum : -sum;
}
LL dfs1(int pos, int sum, int limit)
{
if (pos == 0) return sum;
if (!limit && f[pos][sum] != -1) return f[pos][sum];
int t = limit ? a[pos] : k - 1; LL ans = 0;
for (int i = 0; i <= t; ++i) ans += dfs1(pos - 1, sum + i * (pos - 1), limit && i == a[pos]);
if (!limit) f[pos][sum] = ans;
return ans;
}
LL dfs2(int pos, int sum, int tag, int limit)
{
if (sum < 0) return 0;
if (pos == 0) return sum;
if (!limit && f[pos][sum] != -1) return f[pos][sum];
int t = limit ? a[pos] : k - 1; LL ans = 0;
for (int i = 0; i <= t; ++i) ans += dfs2(pos - 1, sum + ((pos < tag) ? -i : i), tag, limit && i == a[pos]);
if (!limit) f[pos][sum] = ans;
return ans;
}
LL Get(LL p)
{
memset(f, -1, sizeof(f)); cnt = 0;
for (; p; p /= k) a[++cnt] = p % k;
LL sum = dfs1(cnt, 0, 1);
for (int i = 2; i <= cnt; ++i)
{
memset(f, -1, sizeof(f));
sum -= dfs2(cnt, 0, i, 1);
}
return sum;
}
int main()
{
l = read(), r = read(), k = read();
printf ("%lld\n", Get(r) - Get(l - 1));
return 0;
}
总结
数位 DP 的板子好背，但是非常灵活，有的时候具有很大的思维难度。关键点就是能不能想到状态，只要想到了状态，打搜索就轻而易举。