HDU 2089 不要62（数位DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

一道数位DP上手模板题，并且无需考虑前导0的影响。

关于数位DP的资料

https://www.lagou.com/lgeduarticle/9599.html

数位DP 是对数字的“位”进行的和计数有关的DP，数的每一个位称为数位，一个数有个位、十位、百位、千位……数位DP用来解决和数字操作有关的问题，比如某区间内数字和，特定数字问题等。这些问题的数字范围通常很大，无法暴力解决，必须用接近O(logn)的算法。通过DP对“数位”操作，记录算过的区间的状态，用于后续计算快速筛选数字。

数位DP一般会写成记忆化的形式，具有一定的模板性。

其中：pos：当前到第几位。pre：上一位的数字是什么。lead：是否有前导0。limit：是否有上界限制。

其余的便应该很好理解了。

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=505;
 6 int a[maxn];
 7 int dp[20][20];
 8 int DFS(int pos,int pre,int limit){
 9     if(pos==0) return 1;//搜完了，返回1
10     if(limit==0&&dp[pos][pre]!=-1) return dp[pos][pre];
11     int up=limit?a[pos]:9;//是否有上界，如果有上界那么不能超过上界
12     int ans=0;
13     for(int i=0;i<=up;i++){
14         if(i==4) continue;
15         if(pre==6&&i==2) continue;
16         ans+=DFS(pos-1,i,limit&&a[pos]==i);
17     }
18     if(limit==0) dp[pos][pre]=ans;
19     return ans;
20 }
21 int solve(int x){
22     int len=0;
23     memset(dp,-1,sizeof(dp));
24     while(x){
25         a[++len]=x%10;
26         x/=10;
27     }
28     return DFS(len,0,1);//从高位向低位枚举
29 }
30 int main(){
31     int n,m;
32     while(~scanf("%d%d",&n,&m)){
33         if(n==0&&m==0) break;
34         printf("%d
",solve(m)-solve(n-1));//即为[n,m]区间 
35     }
36     return 0;
37 }

AC代码