10 数位DP：数字计数

10数位DP：数字计数

[ZJOI2010] 数字计数

题目描述

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，每个数码(digit)各出现了多少次。

输入格式

仅包含一行两个整数 $a,b$，含义如上所述。

输出格式

包含一行十个整数，分别表示 $0\sim 9$ 在 $[a,b]$ 中出现了多少次。

样例 #1

样例输入 #1

1 99

样例输出 #1

9 20 20 20 20 20 20 20 20 20

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $a\le b\le10^6$；
• 对于 $100\%$ 的数据，保证 $1\le a\le b\le 10^{12}$。

数位DP主要通过记忆化搜索实现，记忆化搜索的本质就是把条件对应的结论记下来，相同条件一定最后对应相同的结论，条件的个数也就决定了DP的维数。

#include <bits/stdc++.h>
#define int long long//注意都要开long long
using namespace std;
int ay[20];
//ay来存这个数每个位子上的数码，倒序存放

int dp[20][2][20][2];
//zero=1表示前面是否全部都是前导零
//limit=1 表示前面对本位有没有限制
//即：前面都是贴着放的为1，前面某一位不是贴着放的，为0；
/*
记忆化搜索。
pos是当前为从高到低位置。limit表示当前位之前的所有位置是否和ay[pos]相等，
                                                    1是相等，0是不相等。
sum表示当前数字出现的次数。zero表示之前是否都是前导0。target是当前在算的数码。
*/
int dfs(int pos,int limit,int sum,int zero,int target)
{
    int ret=0;
    if(pos==0)return sum;//递归终止条件
    if(dp[pos][limit][sum][zero]!=-1)return dp[pos][limit][sum][zero];
    //记搜检索：检索是否已经被记录
    int maxnum=limit?ay[pos]:9;
/*
   由于我们是从高位到低位枚举的，所以如果之前一位的数码和最大数的数码相同，
   这一位就只能枚举到ay[pos]；
   否则如果之前一位比最大数的数码小，那这一位就可以从0~9枚举了。
*/
    for(int i=0;i<=maxnum;i++)
    {
        ret+=dfs(pos-1,limit &&(i==maxnum),sum+((i==target) && (i||!zero)),zero && (i==0),target);
        /*
        继续搜索，数位减一（到下一个位置，倒序存储，从高位到低位），
        limit的更新要看之前有没有相等，且这一位有没有相等；
        sum的更新要看之前是否为前导0或者这一位不是0；
        zero的更新就看之前是否为前导0且这一位继续为0；
        target继续传进去。
        */
    }
    dp[pos][limit][sum][zero]=ret;//记忆化，把搜到的都记下来
    return ret;
}
int part(int a,int d)
{
    int len=0;
    while(a)
    {
        ay[++len]=a%10;
        a/=10;
    }
    memset(dp, -1, sizeof dp);//初始化
    dfs(len,1,0,1,d);
 //开始在第len位上，最高位只能枚举到ay[pos]所以limit是0，sum=0，有前导0。

}
signed main()
{
    int a,b;
    cin>>a>>b;
    for(int i=0;i<=9;i++)
    {
        cout<<part(b,i)-part(a-1,i)<<" ";
    }


    return 0;
}

再来看一道题：

[SCOI2009] windy 数

题目背景

windy 定义了一种 windy 数。

题目描述

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 $a$ 和 $b$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1 10

样例输出 #1

9

样例 #2

样例输入 #2

25 50

样例输出 #2

20

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$。

#include <bits/stdc++.h>
using namespace std;
int ay[100];
int len=0;
int dp[100][100];//dp[i][j]表示搜到第i位，前一位是j，的！limit方案totnum；
//zero=1表示前面是否全部都是前导零
//limit=1 表示前面对本位有没有限制
//即：前面都是贴着放的为1，前面某一位不是贴着放的，为0；
int dfs(int pos,int prenum,int st,int limit)
{//pos当前位置,pre前一位数,st判断前面是否全是0,limit最高位限制
    if(pos>len)return 1;//搜完了 
    if(limit==0 && dp[pos][prenum]!=-1)return dp[pos][prenum];
    //没有最高位限制且已经搜过了
    int maxnum=limit?ay[len+1-pos]:9;//当前位最大数字 
    int ret=0;
    for(int i=0;i<=maxnum;i++)//从0枚举到最大数字 
    {
        if(abs(i-prenum)<2)continue;//不符合题意，继续
        if(i==0 && st==1)ret+=dfs(pos+1,-2,st,limit && (i==maxnum));
        //如果有前导0，下一位随意 
        else ret+=dfs(pos+1,i,0,limit && (i==maxnum));
        //如果没有前导0，继续按部就班地搜 
    }
    if(limit==0 && st==0)dp[pos][prenum]=ret;
//没有最高位限制且没有前导0时记录结果 ，至于为什么要这样，我也不知道，其实可以都记下来的
    return ret;
}
int part(int a)
{
    len=0;
    while(a)
    {
        ay[++len]=a%10;
        a/=10;
    }
    memset(dp, -1, sizeof (dp));
    return dfs(1,-2,1,1);
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<part(b)-part(a-1)<<endl;

    return 0;
}

咱就主打一个看注释吧。