学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=1026

今天开始学数位DP啦~

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
int A,B;
int dp[12][12];
LL base[15];
/////////////////////////////////////////////////
void pre()
{
	base[1]=1;
	rep(i,2,12) base[i]=10*base[i-1];
	rep(i,0,9) dp[1][i]=1;
	rep(i,2,10) rep(j,0,9) rep(k,0,9) if(abs(j-k)>=2)
	{
		dp[i][j]+=dp[i-1][k];
	}
}
int cnt(int n)
{
	if(!n) return 0;
	int d=1,ans=0;
	while(n>=base[d+1])d++;
	rep(i,1,d-1)
		rep(j,1,9)
		    ans+=dp[i][j];
    int last=-1;
    per(i,d,1)
    {
    	int high=n/base[i];
    	rep(j,0,high-1) if(abs(j-last)>=2)
		    ans+=dp[d][j];
	    if(d==1&&abs(last-high)>=2) ans++;
	    d--;
	    if(abs(last-high)<2) break;
	    last=high;
	    n%=base[i];
    }
    return ans;
}
/////////////////////////////////////////////////
void input()
{
    scanf("%d%d",&A,&B);
}
void solve()
{
	pre();
    printf("%d\n",cnt(B)-cnt(A-1));
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),solve();
    return 0;
}