[HDU 2089] 不要62 数位DP(记忆化搜索)

时间:2022-12-16 09:40:42

题目传送门:【HDU 2089】


题目大意:多组数据。求给定区间 [n,m] 中,不含数字串“4”或“62”的数的个数。(0 < n ≤ m < 1000000)
当输入为 n=m=0 时表示输入结束。


题目分析:

本人真正写的第一道数位 DP 题就是它了。
这道题应该是裸的数位 DP。题目中让你求区间中不含“4”或“62”的数的个数,如果我们用记忆化搜索的思想,那么在我们 DFS 的时候,参数里面还需要再记录下上一位数 prev 是多少。如果 prev=6,则接下来的一位就不能取 2。其余情况大致相同,没有太大变化。

For me:我还在 DFS 里加了一个参数 bit,表示我当前 DFS 到的这个数的总位数是多少。防止前导 0 影响最终答案。


下面附上代码:

  1. #include<cstdio>  
  2. #include<cstring>  
  3. #include<iostream>  
  4. #include<algorithm>  
  5. using namespace std;  
  6. typedef long long LL;  
  7. const int MX=10;  
  8.   
  9. int w[MX],f[MX][MX][10],ansa=0,ansb=0;  
  10. //w:记录下每一位数是多少   
  11. //f:总共 i 位数,当前选到第 j 位数,这一位数是 k 的总方案数   
  12.   
  13. int dfs(int bit,int dep,bool limit,bool lead,int prev){  
  14.     if (dep==0){  
  15.         if (!lead) return 1;  
  16.         return 0;  
  17.     }  
  18.       
  19.     int lim=(limit==true ? w[dep] : 9) ,cnt=0,tot=0;                    //cnt:当前这一位取 i 时的方案数   
  20.                                                                         //tot:上一位数为 prev 时的总方案数   
  21.     for (int i=0;i<=lim;i++){  
  22.         if (i==4) continue;  
  23.         if (prev==6 && i==2) continue;  
  24.         if (!limit && !lead && i!=6 && f[bit][dep][i]!=-1){            //记忆化搜索,需要注意”62”,因此前缀为6时继续向下搜   
  25.             cnt=f[bit][dep][i];  
  26.             tot+=cnt;  
  27.             continue;  
  28.         }  
  29.         cnt=dfs(bit-(lead && i==0),dep-1,limit && i==lim,lead && i==0,i);  
  30.         if (f[bit][dep][i]==-1) f[bit][dep][i]=cnt;  
  31.         tot+=cnt;  
  32.     }  
  33.     return tot;  
  34. }  
  35. void _init(){  
  36.     memset(f,-1,sizeof(f));  
  37.     memset(w,0,sizeof(w));  
  38.     ansa=0,ansb=0;  
  39. }  
  40.   
  41. int main(){  
  42.     int a,b;  
  43.     memset(f,-1,sizeof(f));  
  44.     while (scanf(“%d%d”,&a,&b)){  
  45.         if (a==0 && b==0) break;  
  46.         a–;                                                            //前缀和相减   
  47.           
  48.         int wei=0;                              //wei:表示最高位   
  49.         while (b){  
  50.             w[++wei]=b%10;  
  51.             b/=10;  
  52.         }  
  53.         ansb=dfs(wei,wei,true,true,0);  
  54.           
  55.         wei=0;memset(w,0,sizeof(w));  
  56.         while (a){  
  57.             w[++wei]=a%10;  
  58.             a/=10;  
  59.         }  
  60.         ansa=dfs(wei,wei,true,true,0);  
  61.           
  62.         printf(”%d\n”,ansb-ansa);  
  63.         _init();  
  64.     }  
  65.     return 0;  
  66. }