洛谷P2657 [SCOI2009]windy数

#include <bits/stdc++.h>
using namespace std;
long long x;
long long f[12][10];
char num0[15];int len=0;
long long ans=0;
void getans(long long moe){
	scanf("%lld",&x);
	if(moe==-1)x--;
	if(x==0)return;
	len=0;
	if(x==0)len=1;
	while(x)num0[++len]=x%10,x=x/10;
	for(int i=len;i>=1;i--){
		if(i+2<=len&&abs(num0[i+1]-num0[i+2])<=1)break;
		for(int j=0;j<num0[i];j++){
			if(i==len&&j==0)continue;
			if(i+1<=len&&abs(j-num0[i+1])<=1){continue;}
			if(i!=1){
				for(int k=0;k<=9;k++){
					if(abs(k-j)>=2){
						ans+=f[i-1][k]*moe;
					}
				}
			}
			else{
				ans+=moe;
			}
		}
		if((i==1&&abs(num0[1]-num0[2])>=2)||len==1)ans+=moe;
	}
	for(int i=len-1;i>=1;i--)
		for(int j=1;j<=9;j++)
			ans+=moe*f[i][j];
}
int main(){
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=9;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
				if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
	getans(-1);
	getans(1);
	printf("%lld ",ans);
}