luogu2657

思路

数位dp，记录下上个位置的数，如果当前的数字与上个数字的差值小于2，就不再转移。还是要注意排除前导0。在记忆化的时候，全都是前导0的情况不能记忆化。

代码

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

int a[100];

ll f[100][11];

int ab(int x) {

	return x<0?-x:x;

}

int dfs(int pos,int Rea,int limit,int lst) {

	if(!pos) return Rea;

	if(f[pos][lst]!=-1&&Rea&&!limit) return f[pos][lst];

	int up=limit?a[pos]:9;

	ll ans=0;

	for(int i=0;i<=up;++i) {

		if(ab(i-lst)<2&&Rea) continue;

		ans+=dfs(pos-1,Rea||i,limit&&(i==up),i);

	}

	if(!limit&&Rea) f[pos][lst]=ans;

	return ans;

}

int solve(ll x) {

	memset(f,-1,sizeof(f));

	memset(a,0,sizeof(a));

	while(x) {

		a[++a[0]]=x%10;

		x/=10;

	}

	return dfs(a[0],0,1,10);

}

int main() {

	ll x=read(),y=read();

//	cout<<solve(read());

	cout<<solve(y)-solve(x-1);

	return 0;

}