10ptsAC#4求条
查看原帖
10ptsAC#4求条
1398636
yezhengjie0000001楼主2025/7/19 14:33
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
int num[20];
ll dp[20][10];
int len;
ll dfs(int x,int t,bool mx,bool g){
	if(x==0){
		return 1;
	}
	if(!mx&&dp[x][t]!=-1){
		return dp[x][t];
	}
	int m=(mx?num[x]:9);
	ll ans=0;
	for(int i=0;i<=m;i++){
		if(abs(i-t)>=2 || g){
			ans+=dfs(x-1,i,mx&&(i==m),g&&(i==0));
		}
	}
	if(!mx&&g==0){
		dp[x][t]=ans;
	}
	return ans;
}
long long solve(long long x){
    memset(dp,-1,sizeof( dp));
	memset(num,0,sizeof (num));
	len=0;
	if(x==0){
		return 0;
	}
	while(x){
		num[++len]=x%10;
		x/=10;
	}
	ll y=dfs(len,0,1,1);
	return y;
}
int main(){
	cin>>a>>b;
	cout<<solve(b)-solve(a-1)<<'\n';
	return 0;
}
2025/7/19 14:33
加载中...