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

xyx404 · 2025-07-23 11:32:34 · 题解

没学过数位 DP 的可以参考 CSP Wiki。

思路：

考虑数位 DP。

本题只需要在填数时判断一下当前相邻数位差的绝对值之和有没有大于 m 就行了。

具体地，对于每次填数，我们需要考虑，当前相邻数位差的绝对值之和有没有大于 m。

如果大于，返回本次 0 表示没有答案；否则，我们考虑当前数位是否有限制，接着填数，如果最后一位也填了，并且相邻数位差的绝对值之和没有大于 m 就代表本次填的答案是可行的。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL n,m;
LL dp[20][300][11];
int a[20];
int cf(LL x){
    int len=0;
    while(x){
        a[++len]=x%10;
        x/=10;
    }
    return len;
}
LL dfs(LL now,bool xz,bool tg,int sum,int las){
    LL ans=0;
    if(sum>m)return 0;
    if(now==0)return 1;
    if(!xz&&!tg&&dp[now][sum][las]!=-1)return dp[now][sum][las];
    int l=0,r=9;
    if(tg)l=1,ans+=dfs(now-1,0,tg,0,-1);
    if(xz)r=a[now];
    for(int i=l;i<=r;i++){
        ans+=dfs(now-1,(i==r&&xz),0,(las!=-1?sum+abs(i-las):0),i);
    }
    if(!xz&&!tg)dp[now][sum][las]=ans;
    return ans;
}
LL ans(LL x){
    int len=cf(x);
    memset(dp,-1,sizeof dp);
    return dfs(len,1,1,0,-1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cout<<ans(n);
    return 0;
}