数位DP  对新手不太友好。

 

/**************************************************************
    Problem: 1026
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:824 kb
****************************************************************/
 
/*
    数位 DP  最高 10 位数 
    f[i][j]表示i为数 最高位为j的合法数字有多少个
    答案用前缀和思想解决 
    没有较大的数据 总是找不出哪里错了 这似乎对新人不太好 
*/
#include<cstdio>
using namespace std;
const int N=30;
int f[N][N];
long long p[N]={1};
int abs(int x) { return (x>0)?(x):(-x); } 
int Cale(int x)  //计算 1~x-1内的合法数字 
{
    int res=0,l=0,last,a; while(p[l]<=x) l++;
//  printf("l:%d\n",l);
    for(int i=1;i<=l-1;i++) 
    for(int j=1;j<=9;j++) res+=f[i][j];
    a=x/p[l-1];
    for(int i=1;i<a;i++) res+=f[l][i];
    last=a;x%=p[l-1];
    for(int i=l-1;i>=1;i--) //处理第i位 
    {
        a=x/p[i-1];
        for(int j=0;j<a;j++) 
        if(abs(j-last)>=2) res+=f[i][j];
        if(abs(last-a)<2) break;
        last=a; x%=p[i-1];
    }
//  printf("res:%d\n",res);
    return res;
}
void Solve()
{
    for(int i=1;i<=11;i++) p[i]=p[i-1]*10;
    for(int j=0;j<=9;j++) f[1][j]=1; // 预处理第一位 
    for(int i=2;i<=11;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];
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",Cale(r+1)-Cale(l));
//  int x;
//  scanf("%d",&x);
//  printf("%d\n",Cale(x));
}
int main()
{
    Solve();
    return 0;
}