数位 dp 总结
发布日期:2021-06-21 02:54:53 浏览次数:6 分类:技术文章

本文共 2716 字,大约阅读时间需要 9 分钟。

数位 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
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
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]\) 中有多少个满足

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

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

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

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

#include
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 类还是要多练,这几个只是冰山一角

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/116390972 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:2021.05.03【NOIP提高B组】模拟 总结
下一篇:2021.04.24【NOIP提高B组】模拟 总结

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年04月17日 17时32分32秒