13 KiB
数位DP模板
#####原文推荐，致敬作者
一、基础篇
数位dp是一种计数用的dp，一般是要统计一个区间[l,r]内满足一些条件的数的个数。所谓数位dp，字面意思就是在数位上进行dp。数位的含义：一个数有个位、十位、百位、千位......，数的每一位就是数位。
数位dp的本质: 换一种暴力枚举的方式，使得新的枚举方式满足dp的特点，记忆化就可以了。
1、暴力枚举法
求一个区间[l,r]满足条件数的个数，暴力方法如下：
for(int i=l;i<=r;i++)
if(right(i)) ans++;
这样枚举 不方便记忆化 ，或者说根本无状态可言。
2、新的枚举方法
办法:① 控制上界枚举，②从高位向低位枚举
例如：r=213，从百位开始枚举,百位可能的情况有0,1,2 (觉得这里枚举0有问题的继续往后看)
(一)、贴上界
每一位枚举都不能让枚举的这个数超过上界213（下界就是），当百位枚举了0或者1，这个次要1，那么十位枚举就是从0到9，因为百位1已经比上界2小了，后面数位枚举什么都不可能超过上界。所以：当高位(前面所有位，不是指前一位)枚举刚好达到上界时，那么紧接着的一位枚举就有上界限制了。
比如：
- 如果百位枚举了
2，那么十位的枚举情况就是0~1 - 如果前两位枚举了
21，最后一位只能是0~3
【代码模板里的变量
up就是 专门用来判断枚举范围 】
(二)、前导零
最高位枚举0：百位枚举0，相当于此时我枚举的这个数最多是两位数，如果十位继续枚举0，那么我枚举的就是一位数，因为我们要枚举的是小于等于r=213 的所有数，当然不能少了位数比r小的！这样枚举是为了 无遗漏 的枚举，不过可能会带来一个问题，就是 前导零 问题，模板里用lead变量表示，不过这个不是每个题目都是会有影响的，可能前导零不会影响我们计数，具体要看题目。
(三)、前缀和思想
由于这种新的枚举只控制了上界所以我们的main函数总是这样：
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也行， 反正相减后就没了，注意题目中l的范围都是大于等于1的。
3、数位DP模板
在讲例题之前先讲个基本的动态模板(先看后面的例题也行)：
#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;
}
Q:为什么只记录不受限制的数字数量，都记录下来不是更好吗？
-
f数组中记录的结果，其实是不考虑贴上界，不考虑前导零的 结果值，而现实中的情况有时是贴上界或有前导零的,这种情况我们的策略是重新计算，不缓存。 -
前
N位不贴上界，无限制，可以跑满所有可能，记录的所有可能性数字用的上；前N位贴着上界，有限制，当前位置不能跑满，记录的所有可能性数字用不上。 -
op为true的数并不多，一个个枚举不会很浪费时间，所以我们记录下!op的状态解决了不少子问题重叠。 -
有人可能想到把
f状态改一下f[u][st][op]就是分别记录不同op下的个数，这种方法一般是对的，关于这个具体会讲，下面有题bzoj3209会用到这个。
二、实战篇
数位上不能有4也不能有连续的62。
-
没有
4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要 -
对于
62的话，涉及到两位，当前一位是6或者不是6这两种不同情况计数是不相同的，所以要用状态来记录不同的方案数。
\large f[u][st]:当前第u位，根据前一位pre是否是6的状态，这里st只需要取0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。
常用优化
入门就不多讲了，开始讲常用优化吧！
第一: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，如果题目数据少的话就随便你乱搞了)
GG 是good game的意思。随着网络的普及，“GG”的应用亦趋向于日常生活之中，表示“失败”、“结束”、“完蛋了”等含义。
第二：相减
例题：HDU 4734
第三：前导零