前导0的处理是不是写错了
查看原帖
前导0的处理是不是写错了
504142
micmic楼主2022/5/4 17:12
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll; 
//用dp[i][j]代表枚举到第i位,上一位数是i的方案总数 
ll dp[15][15];
int limit[15];
ll L,R;

//pos当前位置,pre前一位数,st判断前面是否全是0,flag最高位限制 
ll dfs(int pos,int pre,int st,int flag){
	if(pos<0) return 1;	//枚举结束 
	//记忆化 
	if(!flag && !st && dp[pos][pre]!=-1) return dp[pos][pre];
	int up=flag?limit[pos]:9;
	int ans=0;
	for(int i=0;i<=up;i++){
		//从0枚举到最大数字
		if(abs(i-pre)<2)continue; //不满足条件,直接跳过这次枚举尝试 
		if (st && i==0) ans+=dfs(pos-1,-2,1,limit&& i==ans); //如果有前导0,下一位随意 
		else ans+=dfs(pos-1,i,0,flag && i==up); 
	}
	if(!flag && !st) dp[pos][pre]=ans;	//没有最高位限制和前导0时记录结果
	return ans; 
}

int solve(ll x){
	int pos=0;
	//分解数位 
	while(x){
		limit[pos++]=x%10;
		x/=10;
	}
	memset(dp,-1,sizeof(dp));
	return dfs(pos-1,0,1,1); 
}

int main(){
	cin>>L>>R;
	cout<<solve(R)-solve(L-1);
}
2022/5/4 17:12
加载中...