全WA悬关求调
查看原帖
全WA悬关求调
920938
XingChen_MoNian楼主2025/1/21 11:21
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
inline ll read(){
	ll f=1,sum=0;char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
int dp[15][15],b[15],a[15];
int dfs(int pos,int num,bool flag1,bool flag2){
	if(!flag1 && !flag2 && dp[pos][num]!=-1) return dp[pos][num];
    if(pos==0) return 1;
	int l=0,r=9;
	if(flag1) r=a[pos-1];
	int tot=0;
	for(int i=l;i<=r;i++){
		if(abs(num-i)<2 && !flag2) continue;
		tot+=dfs(pos-1,i,flag1 && (i==r),flag2 && (i==l));
	}
	if(!flag2 && !flag1) dp[pos][num]=tot;
	return tot;
}
int sol(int r){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
	int id=0;
	while(r){
		b[++id]=r%10;
		r/=10;
	}
	int p=id;
	for(int i=1;i<=id;i++) a[i]=b[id-i+1];
	return dfs(p+1,0,1,1);
}
int main(){
	memset(dp,-1,sizeof(dp));
	int l,r;
	cin>>l>>r;
	int ans=sol(r)-sol(l-1);
	cout<<ans;
	return 0;
}
2025/1/21 11:21
加载中...