- 首先，什么是数位DP？按照我的理解来说，数位DP就是统计某一区间的某些数字（满足某种规定），比如最简单的统计某区间的数字个数（洛谷P2602 [ZJOI2010]数字计数）。然后高级一点的就比如洛谷
P4124 [CQOI2016]手机号码，有几个限制条件。 - 其次，我们应该怎么解决数位·DP这类问题？第一种办法就是推公式（由于本人理解不深，先暂时不讲）。第二种就是记忆化搜索，以个位开始搜出所有可能的状态。
- 这里，我以一道题为例，就是洛谷P4124手机号码。
题目描述
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少 33 个相邻的相同数字；号码中不能同时出现 88 和 44。号码必须同时包含两个特征才满足条件。满足条件的号码例如：13000988721、23333333333、14444101000。而不满足条件的号码例如：1015400080、10010012022。
手机号码一定是 1111 位数，前不含前导的 00。工具接收两个数 LL 和 RR，自动统计出 [L,R][L,R] 区间内所有满足条件的号码数量。LL 和 RR 也是 1111 位的手机号码。
输入格式
输入文件内容只有一行，为空格分隔的 22 个正整数 L,RL,R。
输出格式
输出文件内容只有一行，为 11 个整数，表示满足条件的手机号数量。
- 先来看一下处理的流程：
1.预处理 1.1输入 1.2清零数组 1.3拆位 1.4开始搜索 2.计算符合条件的数字个数 2.1返回不可以的状态 2.2返回只有一位的情况 2.3返回已经计算出结果的情况（也就是记忆化） 2.4循环 2.4.1把所有不符合的状态全部continue掉 2.4.2分类dfs下一个情况 2.4返回答案以及结束本函数 3.输出
- 那么我们再来看一下DFS中需要包括哪些状态：
- 当前所在的位数
- 前一位的数字
- 前两位的数字
- 之前是否已经出现连续三个相同的数字
- 之前是否已经保证x<n
- 号码中是否有’4
- 号码中是否有8
- 好了，这下我们可以开始处理了，还有些小细节会在代码中标注。代码如下：
#include<bits/stdc++.h> #define int long long//个数可能超过int范围 using namespace std; int num[15],dp[15][15][15][2][2][2][2];//当前位数，前一位，前两位，之前是否已经出现连续三个相同的数字，之前是否已经保证x<n，4,8 int dfs(int p,int a,int b,int c,int d,int _4,int _8) { if(_4==1&&_8==1) return 0;//先判断不可能的情况再判断可以的情况 if(p==0) return c; if(dp[p][a][b][c][d][_4][_8]!=-1) return dp[p][a][b][c][d][_4][_8]; int m=d?9:num[p],ans=0; for(int i=0;i<=m;i++) { if(i==4&&_8==1) continue; if(i==8&&_4==1) continue; ans+=dfs(p-1,i,a,c||(i==b&&b==a),d||(i<m),_4||(i==4),_8||(i==8)); } return dp[p][a][b][c][d][_4][_8]=ans; } int work(int x) { if(x<10000000000) return 0; int len=0,rst=0; memset(num,0,sizeof(num)); memset(dp,-1,sizeof(dp)); for(;x;x/=10) { num[++len]=x%10; } for(int i=1;i<=num[len];i++) { rst+=dfs(10,i,0,0,i<num[len],i==4,i==8); } return rst; } signed main() { int l,r; cin>>l>>r; if(l>r)//特判 { printf("0"); return 0; } cout<<work(r)-work(l-1);//注意边界要考虑进去 return 0; }
- 最后，希望本篇博客可以帮助到像我一样的蒟蒻。如有错误以及不足之处，请指出！