dfs记搜30pts求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a,b,ans1,ans2,cnt,dp[14][14];//dp[pos][last_num]
ll arr[14];

ll dfs(ll nums[],ll pos,ll last_num,bool is_max,bool is_zero){
    if(pos==-1){
//    	printf("last_num:%d\n",last_num);
		return 1;
	}
//	printf("pos:%d last_num:%d ",pos,last_num);
//	printf((is_max?"is_max:true ":"is_max:false "));
//	printf((is_zero?"is_zero:true ":"is_zero:false "));
	if(dp[pos][last_num]!=-1){
//		printf("get answer,answer is:%d\n",dp[pos][last_num]);
		return dp[pos][last_num];
	}
//	printf("not get answer\n");
	ll ans=0;
	int upper=(is_max?nums[pos]:9);
	for(ll i=0;i<=upper;i++){
		if(abs(i-last_num)<2&&!is_zero)continue;
		ans+=dfs(nums,pos-1,i,is_max&&i==upper,is_zero&&i==0);
	}
	if(!is_max&&!is_zero){
		dp[pos][last_num]=ans;
	}
	return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    
    memset(dp,-1,sizeof(dp));
    cin>>a>>b;
    a--;
    while(a){
    	arr[cnt++]=a%10;
    	a/=10;
	}
	ans1=dfs(arr,cnt-1,13,1,1);
	cnt=0;
    while(b){
    	arr[cnt++]=b%10;
    	b/=10;
	}
	ans2=dfs(arr,cnt-1,13,1,1);
//	cout<<ans2<<'-'<<ans1<<'='<<ans2-ans1;
	cout<<ans2-ans1;
}