数位DP学习

数位 DP - OI Wiki

引入

主要变量及函数

变量：

        L, R: 所求区间边界

        limit：边界限制，主要在记忆化搜索里用

        len：所求数的位数

        pos：当前所求位置

        lead： 前导零

       DP[N][M] ：第一维是当前的pos，第二位是pos之前位数的限制，用于记忆化搜索，表示这种情况已经整过了，而且是通用的，下次用的时候直接返回即可。

函数：

        以求[l, r]区间0-9各自的个数为例

         主要包括两个函数，

        一个是取数位的函数，cal(n)，直接调用这个函数可得到0-n的符合要求的前缀和，用于初始化和将要求的数的每一位取出来，放进a[N],判断边界的时候用

        另一个是计算每一个数数位的递归函数，dfs(pos, ...,limit),从高位到低位去分析这个数，DP[N][M]存数是主要的剪枝 

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int dp[N][N];
int a[N], len, l, r;

int dfs(int pos, int sum, int num, int lead, int limit)
{
    if(!pos)// 判断到头
    {
        if(lead && !num)return 1; // 前导零并且计数0算记了1个
        return sum;//返回总出现次数
    }
    
    if(!limit && !lead && dp[pos][sum] != -1)return dp[pos][sum];// 记忆化
    
    int res = 0, up = limit ? a[pos] : 9; // 头
    
    for(int i = 0; i <= up; i ++) // 遍历所有情况
    {
        int t;
        if(i == num) // 找到这一位的num
        {
            if(!num)t = sum + (lead == 0); //如果计0的个数并且前导零不加
            else t = sum + 1; // 计数加一
        }
        else t = sum; // t不变
        res += dfs(pos - 1, t, num, lead && i == 0, limit && i == up);
    }
    
    return limit ? res : (lead ? res : dp[pos][sum] = res);
}

int cal(int x, int num)
{
    memset(dp, -1, sizeof dp);
    len = 0;
    while(x)a[++ len] = x % 10, x /= 10;
    return dfs(len, 0, num, 1, 1);
}

int main()
{
    while(cin>>l>>r, l || r)
    {
        if(l > r)swap(l, r);
        for(int i = 0; i <= 9; i ++)cout<<cal(r, i) - cal(l - 1, i)<<' ';
        cout<<endl;
    }
    return 0;
}

一些其他题

​​​​​​​
AcWing 1081. 度的数量活动 - AcWing
AcWing 1082. 数字游戏活动 - AcWing
AcWing 1083. Windy数活动 - AcWing
AcWing 1084. 数字游戏 II活动 - AcWing
AcWing 1085. 不要62活动 - AcWing
AcWing 1086. 恨7不成妻​​​​​​​活动 - AcWing

也可以看下面统计的例题：

知乎