From 18d7a48e9d9447524999e7efdef1297f71ecbff9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E5=BF=83=E6=97=B7=E7=A5=9E=E6=80=A1?= Date: Fri, 31 Aug 2018 19:04:41 +0800 Subject: [PATCH] =?utf8?q?=E4=BF=AE=E6=AD=A3=20dp=20=E6=96=B9=E7=A8=8B?= =?utf8?q?=E4=B9=A6=E5=86=99=EF=BC=9B=E4=B8=BB=E8=A7=82=E6=8E=A8=E5=AE=9A?= =?utf8?q?=E4=B8=80=E5=A5=87=E7=89=B9=E8=A1=A8=E8=BE=BE=E5=BC=8F=E7=9A=84?= =?utf8?q?=E5=90=AB=E4=B9=89?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- docs/dp/number.md | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/docs/dp/number.md b/docs/dp/number.md index 905a5c58..88a862e0 100644 --- a/docs/dp/number.md +++ b/docs/dp/number.md @@ -2,11 +2,11 @@ By [hsfzLZH1](https://github.com/hsfzLZH1) ## 经典题型 -数位 DP 问题往往都是这样的题型，给定一个闭区间 $[l,r]$，让你求这个区间中满足 ** 某种条件 ** 的数的总数。 +数位 DP 问题往往都是这样的题型，给定一个闭区间 $[l,r]$，让你求这个区间中满足 **某种条件** 的数的总数。 -## 例题 [luogu P2657 [SCOI2009]windy 数](https://www.luogu.org/problemnew/show/P2657) +## 例题: [luogu P2657 \[SCOI2009\] windy 数](https://www.luogu.org/problemnew/show/P2657) -题目大意：给定一个区间 $[l,r]$ ，求其中满足条件 ** 不含前导 $0$ 且相邻两个数字相差至少为 $2$ ** 的数字个数。 +题目大意：给定一个区间 $[l,r]$ ，求其中满足条件 **不含前导 $0$ 且相邻两个数字相差至少为 $2$** 的数字个数。 首先我们将问题转化成更加简单的形式。设 $ans_i$ 表示在区间 $[1,i]$ 中满足条件的数的数量，那么所求的答案就是 $ans_r-ans_{l-1}$。 @@ -14,11 +14,11 @@ By [hsfzLZH1](https://github.com/hsfzLZH1) 对于一个小于 $n$ 的数，它从高到低肯定出现某一位，使得这一位上的数值小于 $n$ 这一位上对应的数值。而之前的所有位都和 $n$ 上的位相等。 -有了这个性质，我们可以定义 $f_{i,st,op}$ 表示当前将要考虑的是从高到低的第 $i$ 位，当前该前缀的状态为 $st$ 且前缀和当前求解的数字的大小关系是 $op$ （ $op=1$ 表示等于， $op=0$ 表示小于 ）时的数字个数。在本题中，这个前缀的状态就是上一位的值，因为当前将要确定的位不能取哪些数只和上一位有关。在其他题目中，这个值可以是：前缀的数字和，前缀所有数字的 $gcd$，该前缀取模某个数的余数，也有两种或多种合用的情况。 +有了这个性质，我们可以定义 $f(i,st,op)$ 表示当前将要考虑的是从高到低的第 $i$ 位，当前该前缀的状态为 $st$ 且前缀和当前求解的数字的大小关系是 $op$ （$op=1$ 表示等于，$op=0$ 表示小于）时的数字个数。在本题中，这个前缀的状态就是上一位的值，因为当前将要确定的位不能取哪些数只和上一位有关。在其他题目中，这个值可以是：前缀的数字和，前缀所有数字的 $\gcd$，该前缀取模某个数的余数，也有两种或多种合用的情况。 -写出 ** 状态转移方程 ** ： $f_{i,st,op}=\sum_{i=1}^{maxx} f_{i+1,k,op \& (i=maxx)} (|st-k|\ge 2)$ +写出 **状态转移方程** ： $f(i,st,op)=\sum_{i=1}^{maxx} f(i+1,k,op)\quad (|st-k|\ge 2)$ -这里的 $k$ 就是当前枚举的下一位的值，而 $maxx$ 就是当前能取到的最高位。因为如果 $op=1$ ，那么你在这一位上取的值一定不能大于求解的数字上该位的值，否则则没有限制。 +这里的 $k$ 就是当前枚举的下一位的值，而 $maxx$ 就是当前能取到的最高位。因为如果 $op=1$，那么你在这一位上取的值一定不能大于求解的数字上该位的值，否则则没有限制。 我们发现，尽管前缀所选择的状态不同，而 $f$ 的三个参数相同，答案就是一样的。为了防止这个答案被计算多次，可以使用记忆化搜索的方式实现。 @@ -56,7 +56,7 @@ int solve(int x) ## 几道练习题 -[bzoj 3679 数字之积 ](https://www.lydsy.com/JudgeOnline/problem.php?id=3679) +[BZOJ 3679 数字之积 ](https://www.lydsy.com/JudgeOnline/problem.php?id=3679) [luogu P2602 [ZJOI2010] 数字计数 ](https://www.luogu.org/problemnew/show/P2602) -- 2.11.0