|
|
|
|
|
# 数位$DP$模板
|
|
|
|
|
|
|
|
|
|
|
|
#####[原文推荐，致敬作者](https://blog.csdn.net/wust_zzwh/article/details/52100392)
|
|
|
|
|
|
|
|
|
|
|
|
## 一、基础篇
|
|
|
|
|
|
数位$dp$是一种计数用的$dp$，一般是要统计一个区间$[l,r]$内满足一些条件的数的个数。所谓数位$dp$，字面意思就是在数位上进行$dp$。数位的含义：一个数有个位、十位、百位、千位......，数的每一位就是数位。
|
|
|
|
|
|
|
|
|
|
|
|
数位$dp$的本质: **换一种暴力枚举的方式，使得新的枚举方式满足$dp$的特点，记忆化就可以了**。
|
|
|
|
|
|
|
|
|
|
|
|
### 1、暴力枚举法
|
|
|
|
|
|
求一个区间$[l,r]$满足条件数的个数，暴力方法如下：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
for(int i=l;i<=r;i++)
|
|
|
|
|
|
if(right(i)) ans++;
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
这样枚举 **不方便记忆化** ，或者说根本无状态可言。
|
|
|
|
|
|
|
|
|
|
|
|
### 2、新的枚举方法
|
|
|
|
|
|
#### <font color='red'> 办法:① 控制上界枚举，②从高位向低位枚举</font>
|
|
|
|
|
|
|
|
|
|
|
|
例如：$r=213$，从百位开始枚举,百位可能的情况有$0,1,2$ (觉得这里枚举$0$有问题的继续往后看)
|
|
|
|
|
|
|
|
|
|
|
|
##### (一)、贴上界
|
|
|
|
|
|
每一位枚举都不能让枚举的这个数超过上界$213$（~~下界就是$0$或者$1$，这个次要~~），当百位枚举了$1$，那么十位枚举就是从$0$到$9$，因为百位$1$已经比上界$2$小了，后面数位枚举什么都不可能超过上界。所以：<font color='red'>**当高位(前面所有位，不是指前一位)枚举刚好达到上界时，那么紧接着的一位枚举就有上界限制了**</font>。
|
|
|
|
|
|
|
|
|
|
|
|
比如：
|
|
|
|
|
|
- 如果百位枚举了$2$，那么十位的枚举情况就是$0$~$1$
|
|
|
|
|
|
- 如果前两位枚举了$21$，最后一位只能是$0$~$3$
|
|
|
|
|
|
|
|
|
|
|
|
>【代码模板里的变量$up$就是 **专门用来判断枚举范围** 】
|
|
|
|
|
|
|
|
|
|
|
|
##### (二)、前导零
|
|
|
|
|
|
最高位枚举$0$：百位枚举$0$，相当于此时我枚举的这个数最多是两位数，如果十位继续枚举$0$，那么我枚举的就是一位数，因为我们要枚举的是小于等于$r=213$ 的所有数，当然不能少了位数比$r$小的！这样枚举是为了 **无遗漏** 的枚举，不过可能会带来一个问题，就是 **前导零** 问题，模板里用$lead$变量表示，**不过这个不是每个题目都是会有影响的，可能前导零不会影响我们计数**，具体要看题目。
|
|
|
|
|
|
|
|
|
|
|
|
##### (三)、前缀和思想
|
|
|
|
|
|
由于这种新的枚举只控制了上界所以我们的`main`函数总是这样：
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
int main(){
|
|
|
|
|
|
int l,r;
|
|
|
|
|
|
while(cin >> l >> r && l + r)
|
|
|
|
|
|
printf("%d\n",calc(r)-calc(l-1));
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
统计$[1,r]$数量和$[1,l-1]$，然后相减就是区间$[l,r]$的数量了，这里我写的下界是$1$，其实$0$也行，<font color='blue' size=4><b> 反正相减后就没了</b></font>，注意题目中$l$的范围都是大于等于$1$的。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 3、数位$DP$模板
|
|
|
|
|
|
在讲例题之前先讲个基本的动态模板(先看后面的例题也行)：
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 32; // 输入的数据范围2^31-1,也就是整数上界。2进制是最小的进制，32也够了
|
|
|
|
|
|
int a[N], al;
|
|
|
|
|
|
|
|
|
|
|
|
int f[N][N];
|
|
|
|
|
|
/*
|
|
|
|
|
|
f[i][j]:
|
|
|
|
|
|
i：所在数位第几位，比如469，出发时，就是站在第3位，即4这个位置出发,一般从高位到低位进行，起始值是最高位
|
|
|
|
|
|
j：st的意思，配合位置i,描述一下当前的情况
|
|
|
|
|
|
举个栗子： f[3][4]:走到了位3这个数位，前面已经取得了4个是1的数位，此时，后续的符合条件条件的数有f[3][4]个
|
|
|
|
|
|
第二维还是因题而异的，需要针对不同题目进行思考分析。
|
|
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
|
|
|
|
功能：计算以当前状态出发，会收集到多少个符合条件的数
|
|
|
|
|
|
参数:
|
|
|
|
|
|
u :当前是第几位，比如 421,开始的时候，就是第3位，数值是4
|
|
|
|
|
|
st :记录状态传递变量,比如数字1出现的次数
|
|
|
|
|
|
lead :需不需要考虑前导零
|
|
|
|
|
|
op :是否贴上界
|
|
|
|
|
|
*/
|
|
|
|
|
|
int dfs(int u, int st, bool lead, bool op) {
|
|
|
|
|
|
// 递归边界，既然是按位枚举，最低位是1，那么u==0说明这个数我枚举完了
|
|
|
|
|
|
if (u == 0) return 1; /*这里一般返回1，表示你枚举的这个数是合法的，
|
|
|
|
|
|
那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到u位，
|
|
|
|
|
|
一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
|
|
|
|
|
|
|
|
|
|
|
|
// 第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
|
|
|
|
|
|
// 不贴上界，不需要考虑前导零，以前计算过，这样的东西才能拿来即用
|
|
|
|
|
|
if (!op && !lead && ~f[u][st]) return f[u][st];
|
|
|
|
|
|
|
|
|
|
|
|
/*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
|
|
|
|
|
|
int up = op ? a[u] : 9; // 根据limit判断枚举的上界up;这个的例子前面用213讲过了
|
|
|
|
|
|
int ans = 0;
|
|
|
|
|
|
|
|
|
|
|
|
// 开始计数
|
|
|
|
|
|
for (int i = 0; i <= up; i++) { // 枚举，把不同情况的个数加到ans就可以了
|
|
|
|
|
|
|
|
|
|
|
|
// 这里可以加一些减枝之类的代码
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
|
|
|
|
代码细节：
|
|
|
|
|
|
==的运算优先级 高于 && ，所以先判断 i == a[u]是第一步，与 op 相 && 是第二步
|
|
|
|
|
|
u-1:这玩意是从高位到低位的，由大到小枚举，所以和平常的dfs有点区别，是u-1
|
|
|
|
|
|
|
|
|
|
|
|
逐句解读：
|
|
|
|
|
|
|
|
|
|
|
|
lead && i == 0:
|
|
|
|
|
|
① 如果前面考虑前导0，现在i ==0 ,则后面的数字枚举，仍然要考虑前导零
|
|
|
|
|
|
② 如果前面考虑前导0，现在i>0,则后面的数字枚举，不需要考虑前导零
|
|
|
|
|
|
③ 如果前面不考虑前导0，后面就不用考虑这个前导零的问题
|
|
|
|
|
|
|
|
|
|
|
|
op && i == a[u] :
|
|
|
|
|
|
① 如果原来op=true,即贴上界，而且，当前位枚举的数字i也和原数字位一致，那么后面的数字枚举，必然也继续贴上界
|
|
|
|
|
|
② 如果原来op=false,就是原来就不贴上界，越往后也不会贴上界了
|
|
|
|
|
|
*/
|
|
|
|
|
|
st = st + 1; // 这句话是灵活的，因题而异，一般是描述传递状态的变更，比如选择当前数位的数字1，就多了一个1，需要+1等等
|
|
|
|
|
|
|
|
|
|
|
|
ans += dfs(u - 1, st, lead && i == 0, op && i == a[u]);
|
|
|
|
|
|
/*这里还算比较灵活，不过做几个题就觉得这里也是套路了
|
|
|
|
|
|
大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
|
|
|
|
|
|
去计算不同情况下的个数，还有要根据st变量来保证i的合法性，比如题目
|
|
|
|
|
|
要求数位上不能有62连续出现,那么就是st就是要保存前一位pre,然后分类，
|
|
|
|
|
|
前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法
|
|
|
|
|
|
*/
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 计算完，记录状态
|
|
|
|
|
|
if (!op && !lead) f[u][st] = ans;
|
|
|
|
|
|
/*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
|
|
|
|
|
|
return ans;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 因为用前缀和思想，所以要计算r和l-1两次，封成一个calc函数。
|
|
|
|
|
|
int calc(int x) {
|
|
|
|
|
|
al = 0; // 注意清零，al清零即可，a不用memset清零
|
|
|
|
|
|
// 把数位都分解出来
|
|
|
|
|
|
while (x) a[++al] = x % 10, x /= 10; // 个人喜欢编号为[1,al]
|
|
|
|
|
|
return dfs(al, 0, true, true); // 从最高位开始枚举,刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int l, r;
|
|
|
|
|
|
while (cin >> l >> r) {
|
|
|
|
|
|
// 初始化dp数组为-1
|
|
|
|
|
|
memset(f, -1, sizeof f);
|
|
|
|
|
|
printf("%lld\n", calc(r) - calc(l - 1));
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
<font color='blue' size=4><b>$Q$:为什么只记录不受限制的数字数量，都记录下来不是更好吗？</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
* $f$数组中记录的结果，其实是不考虑贴上界，不考虑前导零的 <font color='blue' size=4><b>结果值</b></font>，而现实中的情况有时是**贴上界**或**有前导零**的,这种情况我们的策略是重新计算，不缓存。
|
|
|
|
|
|
|
|
|
|
|
|
* **<font color='red'>前$N$位不贴上界，无限制，可以跑满所有可能</font>**，记录的所有可能性数字用的上；**<font color='red'>前$N$位贴着上界，有限制，当前位置不能跑满，记录的所有可能性数字用不上</font>**。
|
|
|
|
|
|
|
|
|
|
|
|
* $op$为$true$的数并不多，**一个个枚举**不会很浪费时间，所以我们**记录下`!op`的状态解决了不少子问题重叠**。
|
|
|
|
|
|
|
|
|
|
|
|
* 有人可能想到把$f$状态改一下`f[u][st][op]`就是分别记录不同`op`下的个数，这种方法一般是对的，关于这个具体会讲，下面有题$bzoj3209$会用到这个。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 二、实战篇
|
|
|
|
|
|
|
|
|
|
|
|
> 入门：[$AcWing$ $1085$. 不要$62$](https://www.acwing.com/problem/content/1087/)
|
|
|
|
|
|
|
|
|
|
|
|
数位上不能有$4$也不能有连续的$62$。
|
|
|
|
|
|
* 没有$4$的话在枚举的时候判断一下，不枚举$4$就可以保证状态合法了，所以这个约束没有**记忆化**的必要
|
|
|
|
|
|
|
|
|
|
|
|
* 对于$62$的话，涉及到两位，当前一位是$6$或者不是$6$这两种不同情况计数是不相同的，所以要用状态来记录不同的方案数。
|
|
|
|
|
|
|
|
|
|
|
|
$\large f[u][st]$:当前第$u$位，根据前一位$pre$是否是$6$的状态，这里$st$只需要取$0$和$1$两种状态就可以了，不是$6$的情况可视为同种，不会影响计数。
|
|
|
|
|
|
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/15796194.html)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 常用优化
|
|
|
|
|
|
|
|
|
|
|
|
入门就不多讲了，开始讲常用优化吧！
|
|
|
|
|
|
|
|
|
|
|
|
**第一:`memset(f,-1,sizeof f);`放在多组数据外面。**
|
|
|
|
|
|
|
|
|
|
|
|
这一点是一个数位特点，使用的条件是：**约束条件是每个数自身的属性，而与输入无关**。
|
|
|
|
|
|
|
|
|
|
|
|
具体的：上一个区间不要$62$和$4$，这个约束对每一个数都是确定的，就是说任意一个数满不满足这个约束都是确定，比如$444$这个数，它不满足约束条件，不管你输入的区间是多少,你都无法改变这个数不满足约束这个事实，这就**是数自身的属性**。我们每组数据只是在区间计数而已，只能说你输入的区间不包含$444$的话，我们就不把它统计在内，而无法改变任何事实。
|
|
|
|
|
|
|
|
|
|
|
|
因此，我们保存的状态就可以一直用(注意还有要$limit$，不同区间是会影响数位在有限制条件下的上限的,要配合使用噢，不能想着有了就直接用，要看一下能不能符合当前的限制)
|
|
|
|
|
|
|
|
|
|
|
|
这点优化就不给具体题目了，这个还有进一步的扩展。不过说几个我遇到的简单的约束：
|
|
|
|
|
|
|
|
|
|
|
|
* 求数位和是$10$的倍数的个数,这里简化为数位$sum\%10$这个状态，即$f[u][sum]$这里$10$ 是**与多组无关的**，所以可以`memset`优化，不过注意如果题目的**模是输入的话**那就不能这样了。那样的话，大侠就只能重新来过啦~
|
|
|
|
|
|
|
|
|
|
|
|
* 求二进制$1$的数量与$0$的数量相等的个数，这个也是数自身的属性。
|
|
|
|
|
|
|
|
|
|
|
|
还是做题积累吧。搞懂思想！
|
|
|
|
|
|
|
|
|
|
|
|
下面介绍的方法就是要进行`memset`优化，把不满足前提的通过修改，然后优化。
|
|
|
|
|
|
|
|
|
|
|
|
介绍之前,先说一种较为笨拙的修改，那就是增加状态，前面讲$limit$的地方说增加一维$f[u][st][limit]$，能把不同情况下状态分别记录(不过这个不能`memset`放外面)。
|
|
|
|
|
|
|
|
|
|
|
|
基于这个思想，我们考虑：约束为数位是$p$的倍数的个数，其中$p$数输入的，这和上面$sum\%10$类似，但是$f[u][sum]$显然已经不行了，每次$p$可能都不一样，为了强行把$memset$提到外面加状态$f[u][sum][p]$，对于每个不同$p$分别保存对应的状态。这里前提就比较简单了，你$f$数组必须合法，$p$太大就$GG$了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能$ac$，如果题目数据少的话就随便你乱搞了)
|
|
|
|
|
|
|
|
|
|
|
|
<font color='red' size=4><b>$GG$ 是$good$ $game$的意思。随着网络的普及，“$GG$”的应用亦趋向于日常生活之中，表示“失败”、“结束”、“完蛋了”等含义。</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
**第二：相减**
|
|
|
|
|
|
>> 例题：[HDU 4734](https://vjudge.csgrandeur.cn/problem/HDU-4734)
|
|
|
|
|
|
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/15796422.html)
|
|
|
|
|
|
|
|
|
|
|
|
**第三：前导零**
|
|
|
|
|
|
>> 例题 [$POJ$ $3252$](http://poj.org/problem?id=3252)
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/16677868.html)
|
|
|
|
|
|
|
|
|
|
|
|
>> 例题 [$HUD$ $3709$](http://acm.hdu.edu.cn/showproblem.php?pid=3709)
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/16683570.html)
|
|
|
|
|
|
|
|
|
|
|
|
>> 例题 [$Hbzoj$ $1799$](http://acm.hust.edu.cn/vjudge/problem/19309)
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/16688254.html)
|
|
|
|
|
|
|
|
|
|
|
|
>> 例题 [$HDU$ $4507$](http://acm.hdu.edu.cn/showproblem.php?pid=4507)
|
|
|
|
|
|
[此题解另起博文一篇](https://www.cnblogs.com/littlehb/p/15800476.html)
|
