蒟蒻的数位DP专题总结

///1085422276

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){
        if(ch==‘-‘)f=-1;ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘){
        x=x*10+ch-‘0‘;ch=getchar();
    }return x*f;
}
//****************************************
const int  N=500000+50;
#define mod 1000000007
#define inf 10000007

int dp[11][11][2],vis[11][11][2],d[11];
int dfs(int dep,int pre,int f) {
    if(dep<0) return 1;
    else if(pre>=0&&vis[dep][pre][f]) return dp[dep][pre][f];
    else {
        int re=0;
        if(pre == -1) {
            re+=dfs(dep-1,-1,f||d[dep]>0);
            if(f) for(int i=1;i<=9;i++) re+=dfs(dep-1,i,1);
            else {
                for(int i=1;i<=d[dep];i++) {
                    re+=dfs(dep-1,i,i<d[dep]);
                }
            }
        }
        else  {
            if(f) {
                for(int i=0;i<10;i++) {
                    if(abs(i-pre)>1) {
                        re+=dfs(dep-1,i,1);
                    }
                }
            }
            else {
                for(int i=0;i<10;i++) {
                    if(i<=d[dep]&&abs(i-pre)>1) {
                        re+=dfs(dep-1,i,i<d[dep]);
                    }
                }
            }
        }
        if(pre>=0) vis[dep][pre][f]=1,dp[dep][pre][f]=re;
        return re;
    }
}
int cal(int n) {
   mem(dp);mem(vis);
   int len=0;
   while(n) {
    d[len++]=n%10;n/=10;
   }
   return dfs(len-1,-1,0);
}
int main() {
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF) {
        cout<<cal(b)-cal(a-1)<<endl;
    }
   return 0;
}