Thomasguo666的小屋

一道裸的数位DP题

pos记录搜到了数的第几位，pre记录前一位是哪个数字，lead记录上一位是不是前导零，limit记录上一位是否有最高位限制（也就是这位是否有可能超出搜索的上限）。

#include <bits/stdc++.h>
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define in inline
#define re register
using namespace std;
typedef long long ll;
typedef double db;
in int read()
{
    int ans=0,f=1;char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48);
    return ans*f;
}
int a[15],len;
int f[15][15];
int dfs(int pos,int pre,int lead,int limit)
{
    if (pos>len) return 1;
    if ((!lead)&&(!limit)&&(f[pos][pre]!=-1)) return f[pos][pre];
    int res=limit?a[len-pos+1]:9;
    int ans=0;
    for (int i=0;i<=res;i++)
    {
        if ((!lead)&&abs(i-pre)<2) continue;
        ans+=dfs(pos+1,i,(lead&&!i),limit&&(i==res));
    }
    return ((!lead)&&(!limit))?f[pos][pre]=ans:ans;
}
int solve(int x)
{
    len=0;
    while (x) a[++len]=x%10,x/=10;
    memset(f,-1,sizeof(f));
    return dfs(1,0,1,1);
}
int main()
{
    int a=read(),b=read();
    cout<<solve(b)-solve(a-1)<<endl;
    return 0;
}