专栏文章
题解:P12884 [蓝桥杯 2025 国 C] 整齐的数
P12884题解参与者 5已保存评论 8
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mip1315m
- 此快照首次捕获于
- 2025/12/03 04:26 3 个月前
- 此快照最后确认于
- 2025/12/03 04:26 3 个月前
这是一道数位 dp 模版题。
如果你不知道什么是数位 dp ,请先去学习。
这道题的思路很简单,和P4999 烦人的数学作业有点像,大概思路就是在搜索的时候判断一下绝对值之和是否超过范围,还有就是注意一下前导零,如果有前导零的话,那么第一位非零数字与上一位数字之差为零。
详细请见代码:
CPP#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;
}
相关推荐
评论
共 8 条评论,欢迎与作者交流。
正在加载评论...