数位DP——洛谷P4124 [CQOI2016]手机号码

输出文件内容只有一行，为 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;
  } 
  

• 最后，希望本篇博客可以帮助到像我一样的蒟蒻。如有错误以及不足之处，请指出！