专栏文章

题解: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 条评论,欢迎与作者交流。

正在加载评论...