题解：P12884 [蓝桥杯 2025 国 C] 整齐的数

· · 题解

这是一道数位 dp 模版题。

如果你不知道什么是数位 dp ，请先去学习。

这道题的思路很简单，和P4999 烦人的数学作业有点像，大概思路就是在搜索的时候判断一下绝对值之和是否超过范围，还有就是注意一下前导零，如果有前导零的话，那么第一位非零数字与上一位数字之差为零。

详细请见代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,num[20],dp[20][205][10],cnt;
int dfs(int pos,int limit,int lead,int sum,int last){//模版 
    /*
    pos表示还剩几位数字没有搜索，limit表示取值是否有限制，lead记录前导零
    sum记录和，last记录上一位 
    */ 
    if(sum>m)return 0;//总和超过 m，一定不行，直接结束 
    if(pos==0)return 1;//可以返回1，表示找到一个可行的数字 
    if(!limit&&lead&&dp[pos][sum][last]!=-1)return dp[pos][sum][last];//记忆化 
    int ans=0,up=9;
    if(limit)up=num[pos];//up表示当前位可取的最大数 
    for(int i=0;i<=up;i++){
        int temp;
        if(!lead)temp=0;//temp 用来计算差值，如果lead=0，即有前导零，则差值为零 
        else temp=abs(last-i);
        ans+=dfs(pos-1,limit&&(i==up),lead||i,sum+temp,i);
    }
    if(!limit&&lead)dp[pos][sum][last]=ans;//只有！limit&&lead时dp才会更新 
    return ans;
}
void deal(int x){
    memset(dp,-1,sizeof(dp));//记得初始化 
    cnt=0;
    while(x){
        num[++cnt]=x%10;
        x/=10;
    }
    printf("%lld",dfs(cnt,1,0,0,0));
}
signed main(){
    scanf("%lld%lld",&n,&m);
    deal(n);
    return 0;
}