数位 dp 总结

特征

问你一个区间 \([L,R]\) 中符合要求的数的个数

一个简单的 trick ：把答案拆成前缀和 \(Ans(R)-Ans(L-1)\)

如何求 \(Ans()\) ，就要用到数位 dp

核心

其实就是记忆化搜索，不建议用循环实现，一是麻烦，二是不会

一般地，设 \(f_{x,\cdots,op}\) 为从最高位到第 \(x\) 位满足一些状态时是否时上一位是否是最高位

只要先将 \(v\) 按照题目要求拆到数组里，然后进行 dfs 算答案即可

递归边界：若 \(x=0\) ，检查当前状态是否合法并返回

有前导零的情况，需要多一个参数

int dfs(int x,...,int op) {

	if(!x)return ...;

	if(~f[x][...][op])

		return f[x][...][op];

	register int mx=op?num[x]:1,res=0;

	for(int i=0;i<=mx;i++)

		res+=dfs(x-1,...,op&(i==mx));

	return f[x][...][op]=res;

}

例 1 windy 数

求区间内有多少不含前导零且相邻两个数字之差至少为 2 的正整数

记录上一个数是多少即可，还可以顺便判断前导零的情况

#include<bits/stdc++.h>

using namespace std;

int L,R,len,num[20],f[20][20][2];

int dfs(int x,int ls,int op) {

	if(!x)return 1;

	if(~f[x][ls][op])return f[x][ls][op];

	register int mx=op?num[x]:9,res=0;

	for(int i=0;i<=mx;i++) {

		if(abs(ls-i)<2)continue;

		if(!i && ls==15)

			res+=dfs(x-1,15,op&(i==mx));

		else res+=dfs(x-1,i,op&(i==mx));

	}

	return f[x][ls][op]=res;

}

inline int Ans(int x) {

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

	len=0;

	for(;x;x/=10)num[++len]=x%10;

	return dfs(len,15,1);

}

int main() {

	while(scanf("%d%d",&L,&R)!=EOF)

		printf("%d",Ans(R)-Ans(L-1));

}

例 2 Round Numbers S

如果一个正整数的二进制表示中，0 的数目不小于 1 的数目，那么它就被称为「圆数」。

计算区间 \([l,r]\) 中有多少个「圆数」。

分别记录 0 的个数和 1 的个数，需要判断前导零，记得用二进制

#include<bits/stdc++.h>

using namespace std;

int L,R,len,num[40],f[40][40][40][2];

int dfs(int x,int s0,int s1,int op,int fir) {

	if(!x)return s0>=s1;

	if(~f[x][s0][s1][op])

		return f[x][s0][s1][op];

	register int mx=op?num[x]:1,res=0;

	for(int i=0;i<=mx;i++) {

		if(fir && !i)res+=dfs(x-1,0,0,op&(i==mx),1);

		else res+=dfs(x-1,s0+(i==0),s1+(i==1),op&(i==mx),0);

	}

	return f[x][s0][s1][op]=res;

}

inline int Ans(int x) {

	memset(f,-1,sizeof(f)),len=0;

	while(x)num[++len]=x&1,x>>=1;

	return dfs(len,0,0,1,1);

}

int main() {

	scanf("%d%d",&L,&R);

	printf("%d",Ans(R)-Ans(L-1));

}

例 3 [CQOI2016]手机号码

计算区间 \([l,r]\) 中有多少个满足

有三个相同数相邻
不能同时出现 8 和 4

记录上一个数 \(l1\)，上上个数 \(l2\)，是否有连续三个 \(p3\)，是否有 8 \(p8\)，是否有 4 \(p4\)

如果只用考虑一个前导零可以直接枚举第一位

坑：如果不满足位数要返回 0

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL L,R,f[20][10][10][2][2][2][2];

int num[20],len;

LL dfs(int x,int l1,int l2,int p3,int p4,int p8,int op) {

	if(p4 && p8)return 0;

	if(!x)return p3;

	if(~f[x][l1][l2][p3][p4][p8][op])

		return f[x][l1][l2][p3][p4][p8][op];

	register int mx=op?num[x]:9;

	register LL res=0;

	for(int i=0;i<=mx;i++)

		res+=dfs(x-1,i,l1,p3|(i==l1 && i==l2),p4|(i==4),p8|(i==8),op&(i==mx));

	f[x][l1][l2][p3][p4][p8][op]=res;

	return res;

}

inline LL Ans(LL x) {

	memset(f,-1,sizeof(f)),len=0;

	while(x)num[++len]=x%10,x/=10;

	if(len^11)return 0;

	register LL ans=0;

	for(int i=1;i<=num[len];i++)

		ans+=dfs(10,i,0,0,i==4,i==8,i==num[len]);

	return ans;

}

int main() {

	scanf("%lld%lld",&L,&R);

	printf("%lld",Ans(R)-Ans(L-1));

}

最后

dp 类还是要多练，这几个只是冰山一角

巴特西

数位 dp 总结

数位 dp 总结

特征

核心

例 1 windy 数

例 2 Round Numbers S

例 3 [CQOI2016]手机号码

最后

最新文章

热门文章