Chlience

【算法】数位DP 从入门到摔门
数位DP 不是很水么您说得对,说得对 Orz基础数位DP一般是一种计算 $[l,r]$ 区间中有多少满足条件的数的...
扫描右侧二维码阅读全文
02
2018/11

【算法】数位DP 从入门到摔门

数位DP 不是很水么

您说得对,说得对 Orz

基础

数位DP一般是一种计算 $[l,r]$ 区间中有多少满足条件的数的DP,因为条件常常和数字每一位之间的关系有关所以开发出了数位DP

数位DP的实质是优化状态,简化转移

显然,最原始的状态每个状态只保存对应的一个数字,那么大概是这样

for(int i = l ; i <= r ; ++ i)
    ans += check(i);

这也就是通常所说的枚举

然而在一般的题目之中,有很多的数都是等价的,我们就可以将其压入一个状态中

比如说:求 $[l , r]$ 中不含有数字 $7$ 的个数

对于这个限制,前 $i$ 位不含 $7$ 的数字就是等价的,那么就将其放到一起,设为 $f[i][0]$;含 $7$ 的同理,设为 $f[i][1]$

所以我们只需要枚举最新的一位放的是不是 $7$ 就可以得到转移方程:$f[i][0] = f[i - 1][0] * 9 , f[i][1] = f[i - 1][1] + f[i - 1][0]$

当然,在这里 $f[i][0]$ 对答案没有影响,不转移也罢

到这里有可能会问了:如果我枚举的时候超过限制了咋办?

首先为了方便,我们将 $[l ,r]$ 转化为 $[1 , r] - [1 , l - 1]$ ,这样便只需要处理两个前缀

考虑到当前面所有位都取到最大值,达到 $limit$ 时,当前位有限制,所以从高位往低位枚举,并且将前面取到最大值的情况拿出来单独转移

//首先单独处理第一位
f[1][0] = a[i] - 1;//因为没有前导 0 所以第一位不选 0 ,并且也不选最大值,防止枚举当前位时超过限制
if(a[i] > 7) f[1][0] --;//不选 7 ,同时考虑下是不是和最大值重复
if(a[i] == 7) flag = 1;//如果取到最大值时有 7 ,那么最大值序列就不能继续向下转移了
for(int i = 2 ; i <= lenth ; ++ i) {
    //这是前面没有限制的情况
    f[i][0] = f[i - 1][0] * 9;//不能选 7 ,其他任选
    f[i][1] = f[i - 1][1] + f[i - 1][0];//以前就选了 7 和这次选了 7 的情况
    //前面均达到限制的情况
    if(!flag) {
        //在这里我们同样不选最大值,那么就可以加入 [0 , a[i] - 1] 到非最大值数组中,也就是以后的转移没有限制的数组
        f[i][0] += a[i];
        
        //考虑把 7 选进去了的情况,就删掉 7 
        if(a[i] > 7) {f[i][0] --; f[i][1] ++;}
        
        //如果限制死了这一位选 7 那么显然后面不管选啥都不可能有贡献
        if(a[i] == 7) flag = 1;
    }
    else f[i][1] += a[i] + 1;//这就属于前面到达限制时有 7 的情况
}

如果你认真理解了这份代码,你会发现有两个问题

  1. 其实我们取不到 $[1 , x]$ ,而是只能取到 $[1 , x - 1]$
  2. 只能处理没有前导零的情况

对于第一个问题,是显然的,因为并没有处理最后一位取到最大值的答案(认真观察会发现每一位取到最大值的贡献是在处理下一位时一起算的),所以特判一下

对于第二个问题,只需要将 $9 , 99 , 999 \cdots$ 的答案弄个前缀和就行了

当然你也可以在第一位时将 0 选入,只不过有些特殊的题目可能要进行比较复杂的处理,具体题目具体分析吧

学到这里,基本的框架就出来了,当然,我这里用循环枚举代替了 DFS,如果想用 DFS 的可以参阅 另外一个大佬的博客(估计你已经看过了QwQ)

那么,DP部分如何解决,状态怎么设立呢?

显然,考虑一下每个数字对于答案的贡献的共性,一般都是和数位有关(要不然叫什么数位 DP),存下和题目限制有关的数位即可

例题

当然,光说不练是没啥用的,提供两道例题,具体讲解请看链接

HDU 2089 不要62

题解

HDU 4507 吉哥系列故事——恨7不成妻

题解

Nowcoder 210C 好朋友

题解

后续也会继续更新!

Last modification:November 2nd, 2018 at 09:59 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment