小学生都能看懂的数位dp

简介

数位$dp$归为计数$dp$，通常需要统计一个区间$[L,R]$内满足某些限制条件的个数

前言

数位dp其实很久前就知道了，也做过几道和其他算法混在一起的题目，其实通过手玩是能做的

但毕竟是种算法，还是系统学下比较好(节省手玩时间)

模板题

P2602 [ZJOI2010]数字计数

求$[L,R]$间，$0$到$9$在数位上出现的次数

设数组$dp_i$为满$i$位每个数字出现的次数，也是说四位我们都算进去而忽略前导0的存在

而实际中显然像0012这样的数字我们是不会统计那两个0的

(满位情况下每个数字出现次数相同故我们可以公用空间)

则$dp_i=dp_{i-1}+10^{i-1}$，理解？？

比如从一位到两位：

$1.$$0$_{$9$在第一位各出现一次，到两位时它们前面补上$0$}$9$(第一位为0：00,10......90)故在$dp_{i-1}$基础上乘$10$

$2.$不仅要算原有位出现的次数，新加的该位也要算(第二位为1:10,11......19)，数满$i-1$位，故加上$10^{i-1}$

当然你也可以手玩一遍验证一下

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL dp[20],tmp[20],a[20];

int main(){

    dp[0]=0,tmp[0]=1;

    for(LL i=1;i<=4;++i){

    	dp[i]=dp[i-1]*10+tmp[i-1],

		tmp[i]=tmp[i-1]*10;

	}

	for(LL i=0;i<=9999;++i)

		for(LL j=1,bit=i;j<=4;++j)

			++a[bit%10],

			bit/=10;

	printf("%lld",dp[4]);printf("\n");

	for(LL i=0;i<=9;++i)

	    printf("%lld ",a[i]);printf("\n");

    return 0;

}

现在来考虑前导$0$，第$i$位为前导$0$时，实际上我们多算了填满$i-1$位的次数，减去就好

My complete code(代码有少量注释，应该容易看懂)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

typedef long long LL;

inline LL Read(){

	LL x(0),f(1);char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*f;

}

LL l,r;

LL a[20],cover[20],dp[20],countl[20],countr[20];

inline void Solve(LL num,LL *A){

	LL len(0),bit=num;

	while(num){

		a[++len]=num%10,num/=10;

	}

	for(LL i=len;i>=1;--i){

		for(LL j=0;j<10;++j)

		    A[j]+=dp[i-1]*a[i];//有第i位时的贡献

		for(LL j=0;j<a[i];++j)

		    A[j]+=cover[i-1];//i-1位以下的贡献

		bit-=a[i]*cover[i-1],

		A[a[i]]+=bit+1,//第i位上的该数未补满i-1位

		A[0]-=cover[i-1];//减去前导0的个数

	}

}

int main(){

	cover[0]=1;

	for(LL i=1;i<=16;++i){

		dp[i]=(dp[i-1]<<3)+(dp[i-1]<<1)+cover[i-1],

		cover[i]=(cover[i-1]<<3)+(cover[i-1]<<1);

	}

	l=Read(),r=Read(),

	Solve(l-1,countl),

	Solve(r,countr);

	for(LL i=0;i<10;++i)

	    printf("%lld ",countr[i]-countl[i]);

	return 0;

}

再用类似的方法做道题

[SCOI2009]windy数

求$[L,R]$间不含前导零且相邻两个数字之差至少为2的个数

我们用$dp_{i,j}$表示前$i$位，第$i$位为$j$的方案数$($稍微做过点动规的人这个都不成问题吧$)$

考虑$Solve(x)$为求$x$以内的答案

分三部分做$($设$len$为数位，每一位为$a_i)$

只有$len-1$位的答案$\sum\limits_{i=1}^{len-1}\sum\limits_{j=1}^9 dp_{i,j}$

有$len$位，但最高位未顶着上界，答案为$\sum\limits_{i=1}^{a_{len}-1} dp_{len,i}$

有$len$位，且从最高位到$i+1$连续一段都顶着上界，最后答案为$\sum\limits_{i=1}^{len-1}\sum\limits_{j=0}^{a_i-1}dp_{i,j}$

但我们发现顶着上界的那部分也得满足条件$($差值至少为$2)$

但我们发现其实是在计算$x-1$以内的答案$($第三部分使得最低位统计不到上界$)$

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL l,r;

LL dp[15][10],a[15];

inline void Calc(){

	for(LL i=0;i<=9;++i) dp[1][i]=1;

	for(LL i=2;i<=10;++i)

	    for(LL j=0;j<=9;++j)

	        for(LL k=0;k<=9;++k)

	            if(abs(j-k)>=2)

				    dp[i][j]+=dp[i-1][k];

}

inline LL Solve(LL x){

	LL len(0),tmp(x),ret(0);

	while(tmp) a[++len]=tmp%10,tmp/=10;

	for(LL i=len-1;i>=1;--i){

	    for(LL j=0;j<a[i];++j)

		    if(abs(j-a[i+1])>=2)

			    ret+=dp[i][j];

		if(abs(a[i]-a[i+1])<2) break;

	}

	for(LL i=1;i<a[len];++i) ret+=dp[len][i];//最高位为1~x-1 

	for(LL i=1;i<len;++i)

	    for(LL j=1;j<=9;++j)

		    ret+=dp[i][j];

	return ret;

}

int main(){

	Calc();

	scanf("%lld%lld",&l,&r);

	printf("%lld",Solve(r+1)-Solve(l));

	return 0;

}

更无脑的方法

用记忆化搜索来做，抛开循环后转移状态能更加随意，大部分数位动规的题都可随意切

拿上题举例，我们用$Dfs(now,num,top)$表示遍历到第$now$位，上一位为$num$，是否顶着上界

每层确定这一位选啥，判断是否和上一位冲突，全部确定完了方案数$+1$

由于顶着上界是比较特殊的情况，所以这类答案单独计算，不用记忆化，其他(不顶着上界)的情况用$f_{now,num}$表示$Dfs(now,num,0)$的答案
最后算一下最高位为$0$的情况

#include<bits/stdc++.h>

typedef long long LL;

LL l,r;

LL f[11][10],a[11],dp[11][10];

inline void Calc(){

    for(LL i=0;i<=9;++i) dp[1][i]=1;

    for(LL i=2;i<=10;++i)

        for(LL j=0;j<=9;++j)

            for(LL k=0;k<=9;++k)

                if(abs(j-k)>=2)

                    dp[i][j]+=dp[i-1][k];

}

LL Dfs(LL now,LL num,LL top){

    if(!now) return 1;

    if(!top && f[now][num]) return f[now][num];

    LL Up(top?a[now]:9),ret(0);

    for(LL i=0;i<=Up;++i)

        if(abs(num-i)>=2)

            ret+=Dfs(now-1,i,top&&(i==Up));

    if(!top) f[now][num]=ret;

    return ret;

}

inline LL Solve(LL num){

    LL tot(0);

    while(num){

        a[++tot]=num%10;

        num/=10;

    }

    LL ret(0);

    for(LL i=1;i<=a[tot];++i) ret+=Dfs(tot-1,i,i==a[tot]);

    for(LL i=tot-1;i>=1;--i)

        for(LL j=1;j<=9;++j)

            ret+=dp[i][j];

    return ret;

}

int main(){

    Calc();

    scanf("%lld%lld",&l,&r);

    printf("%lld\n",Solve(r)-Solve(l-1));

    return 0;

}

其他题目

搜索的方法相比纯循环计算，由于上道题限制较少难度简单，故显得有点鸡肋

[CQOI2016]手机号码

11位的手机号，在$[L,R]$求出满足两个条件的方案数：至少有三位连续的数字相同，不能同时出现$4$和$8$，

$Dfs(now,p,pp,\_4,\_8,top,hw)$

分别表示到第几位了，前一位数字，前两位数字，是否出现过$4/8$，是否顶着上界，是否出现过了三连

用冗长的七重循环直接番了五倍的代码量

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL l,r;

LL f[12][10][10][2][2][2],a[20];

LL Dfs(LL now,LL p,LL pp,LL _4,LL _8,LL top,LL hw){

	if(_4&&_8) return 0;

	if(!now) return hw;

	if(!top && f[now][p][pp][_4][_8][hw]!=-1) return f[now][p][pp][_4][_8][hw];

	LL Up=top?a[now]:9;

	LL ret(0);

	for(LL i=0;i<=Up;++i)

	    ret+=Dfs(now-1,i,p, _4|(i==4),_8|(i==8), top&&(i==Up) ,hw|(i==pp&&i==p));

	if(!top) f[now][p][pp][_4][_8][hw]=ret;

	return ret;

}

inline LL Solve(LL x){

	LL tot(0);

	while(x){

		a[++tot]=x%10;

		x/=10;

	}

	if(tot!=11) return 0;

	LL ret(0);

	for(LL i=1;i<=a[tot];++i)

	    ret+=Dfs(tot-1,i,0,(i==4),(i==8),i==a[tot],0);

	return ret;

}

int main(){

	cin>>l>>r;

	memset(f,-1,sizeof(f));

	cout<<Solve(r)-Solve(l-1);

	return 0;

}

总结

搜索与循环异曲同工之妙，但前者更易转移状态，在限制较多的情况下被大部分人喜爱，但后者更能锻炼码力权衡利弊后均可放心食用

搜索的常见模板

LL Dfs(LL now,限制,LL top){

	if(!now) return 判断条件;

	if(!top && f[now][...]) return f[now][...];

	LL Up=top?a[now]:9;

	LL ret(0);

	for(LL i=0;i<=Up;++i)

	    ret+=Dfs(now-1,...,top&(i==Up));

	if(!top) f[now][...]=ret;

	return ret;

}

inline LL Solve(LL x){

	LL tot(0);

	while(x){

		a[++tot]=x%10;

		x/=10;

	}

	Dfs(....);

	return ret;

}

小学生都能看懂的数位dp

简介

前言

模板题

再用类似的方法做道题

更无脑的方法

其他题目

总结