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

2022-07-23 19:39:37

首先，什么是数位DP？按照我的理解来说，数位DP就是统计某一区间的某些数字（满足某种规定），比如最简单的统计某区间的数字个数（洛谷P2602 [ZJOI2010]数字计数）。然后高级一点的就比如洛谷
P4124 [CQOI2016]手机号码，有几个限制条件。
其次，我们应该怎么解决数位·DP这类问题？第一种办法就是推公式（由于本人理解不深，先暂时不讲）。第二种就是记忆化搜索，以个位开始搜出所有可能的状态。
这里，我以一道题为例，就是洛谷P4124手机号码。

题目描述

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。

工具需要检测的号码特征有两个：号码中要出现至少

手机号码一定是

输入格式

输入文件内容只有一行，为空格分隔的

输出格式

输出文件内容只有一行，为

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;
}

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

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

码农公寓

相关文章