求助
查看原帖
求助
570505
dcy0709楼主2023/8/13 13:53
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
int dp[100005][15];
int c[100005],d[100005];
	long long aa,b;
		int i=2;
int a[105];
int dfs(int pos,int x,int flag1,int flag2){
	if(pos==i+1){
		return 1;
	}
	if(!flag1&&!flag2&&dp[pos][x]!=-1){
		return dp[pos][x];
	}
	int mx=9;
	if(flag2){
		mx=a[pos+1];
	}
	int ans=0;
	for(int i=0;i<=mx;i++){
		if(abs(i-x)>=2||flag1)
		ans+=dfs(pos+1,i,(i==0)&flag1,flag2&(i==a[pos+1]));
	}
	if(flag1||flag2){
		return ans;
	}
	else{
		return dp[pos][x]=ans;
	}
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>aa>>b;
	int l=aa-1,r=b;
	i=0;
	while(l){
		a[++i]=l%10;
		l/=10;
	}
	
	int jj=dfs(1,0,1,1);
	i=0;
	memset(a,0,sizeof(a));
	memset(dp,-1,sizeof(dp));
	while(r){
		a[++i]=r%10;
		r/=10;
	}
	int jjj=dfs(1,0,1,1);
	cout<<jjj-jj;
    return 0;
}
2023/8/13 13:53
加载中...