满江紫求助
查看原帖
满江紫求助
746237
SaintRelief楼主2023/8/19 22:06
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=11;
int f[N][N];
void init(){
	for(int i=0;i<=9;i++)
	{
		f[1][i]=1;
	}
	for(int i=2;i<N;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=0;k<=9;k++)
			{
				if(abs(k-j)<2) continue;
				f[i][j]+=f[i-1][k];
			}
		}
	}
}
int calc(int x){
	if(x==0) return 1;
	int a[N]={0};
	int n=0;
	while(x){
		a[++n]=x%10;
		x/=10;
	}
	int res=0;
	int last=0;
	for(int i=1;i<n;i--)
	{
		for(int j=0;j<=9;j++)
		{
			res+=f[i][j];
		}
	}
	for(int i=1;i<a[n];i++) res+=f[n][i];
	for(int i=n-1;i>=1;i--)
	{
		for(int j=0;j<a[i];j++)
		{
			if(abs(a[i+1]-j)<2)continue;
			res+=f[i][j];
		}
		if(abs(a[i+1]-a[i])<2) break;
	}
	return res;
}
signed main(){
	init();
	int l,r;
	cin>>l>>r;
	cout<<calc(r+1)-calc(l)<<'\n';
	return 0;
}
2023/8/19 22:06
加载中...