10pts求调
查看原帖
10pts求调
288506
OutsideR_楼主2024/3/29 16:40
#include<iostream>
using namespace std;
int a,b;
long long dp[11][11];
int abs(int x){
	if(x<0)return -x;
	return x;
}
long long f(int k){
	int a[10],length=1;
	long long ans=0;
	if(k>=0 && k<=9)return k;
	while(1){
		if(k<10){
			a[length]=k;
			break;
		}
		a[length]=k%10;
		k/=10;
		length++;
	}
	for(int t=1;t<length;t++){
		for(int i=0;i<=9;i++)ans+=dp[t][i];
	}
	for(int i=0;i<a[length];i++)ans+=dp[length][i];
	for(int i=length-1;i>=1;i--){
		for(int j=0;j<a[i];j++){
			if(abs(a[i+1]-j)>=2)ans+=dp[i][j];
		}
		if(abs(a[i+1]-a[i])<2)break;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	for(int i=0;i<=9;i++)dp[1][i]=1;
	for(int i=2;i<=9;i++){
		for(int j=3;j<=9;j++)dp[i][1]+=dp[i-1][j]; 
		for(int t=2;t<=9;t++){
			for(int j=0;j<=t-2;j++)dp[i][t]+=dp[i-1][j];
			for(int j=t+2;j<=9;j++)dp[i][t]+=dp[i-1][j]; 
		}
	}
	cout<<f(b+1)-f(a)<<endl;
	return 0;
}

RT,悬关

2024/3/29 16:40
加载中...