You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
python/TangDou/AcWing/ShuWei/数位dp总结 之 从入门到模板.md

13 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

数位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,那么十位枚举就是从09,因为百位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这个位置出发,一般从高位到低位进行,起始值是最高位
jst的意思配合位置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位贴着上界,有限制,当前位置不能跑满,记录的所有可能性数字用不上

  • optrue的数并不多,一个个枚举不会很浪费时间,所以我们记录下!op的状态解决了不少子问题重叠

  • 有人可能想到把f状态改一下f[u][st][op]就是分别记录不同op下的个数,这种方法一般是对的,关于这个具体会讲,下面有题bzoj3209会用到这个。

二、实战篇

入门:AcWing 1085. 不要62

数位上不能有4也不能有连续的62

  • 没有4的话在枚举的时候判断一下,不枚举4就可以保证状态合法了,所以这个约束没有记忆化的必要

  • 对于62的话,涉及到两位,当前一位是6或者不是6这两种不同情况计数是不相同的,所以要用状态来记录不同的方案数。

\large f[u][st]:当前第u位,根据前一位pre是否是6的状态,这里st只需要取01两种状态就可以了,不是6的情况可视为同种,不会影响计数。

此题解另起博文一篇

常用优化

入门就不多讲了,开始讲常用优化吧!

第一:memset(f,-1,sizeof f);放在多组数据外面。

这一点是一个数位特点,使用的条件是:约束条件是每个数自身的属性,而与输入无关

具体的:上一个区间不要624,这个约束对每一个数都是确定的,就是说任意一个数满不满足这个约束都是确定,比如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,如果题目数据少的话就随便你乱搞了)

GGgood game的意思。随着网络的普及,“GG”的应用亦趋向于日常生活之中,表示“失败”、“结束”、“完蛋了”等含义。

第二:相减

例题:HDU 4734

此题解另起博文一篇

第三:前导零

例题 POJ 3252 此题解另起博文一篇

例题 HUD 3709 此题解另起博文一篇

例题 Hbzoj 1799 此题解另起博文一篇

例题 HDU 4507 此题解另起博文一篇