你好,我的思路和你差不多,可以看一下我的代码
```cpp
#include<iostream>//windy数,记忆化搜索 ,数位dp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#define reg register int
#define ll long long
using namespace std;
int f[20][20],l,r;
ll Dim[20]={0};
inline int read()
{
int x=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')
f=-1;
for(;isdigit(c);c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline ll Dfs(ll x,ll pre,ll bj)//bj是连着的
{
if(!x)return 1;
if(!bj&&f[x][pre]!=-1)return f[x][pre];
ll maxn=bj? Dim[x]:9;
ll tmp=0;
for(reg i=0;i<=maxn;++i)
{
if(abs(pre-i)<2)continue;
if(pre==11&&i==0)/*上一位也为0*/tmp+=Dfs(x-1,11,bj&&i==maxn/*持续压位*/);//这句是特判0的情况
else tmp+=Dfs(x-1,i,bj&&i==maxn);
}
if(!bj)f[x][pre]=tmp;
return tmp;
}
inline ll Count(int x)
{
Dim[0]=0;
while(x)//逆序高精
{
Dim[++Dim[0]]=x%10;
x/=10;
}
return Dfs(Dim[0],11,1);//因为pre为11时,9是可枚的 ,并且一开始压位肯定是要报警的
}
int main()
{
memset(f,-1,sizeof(f));
l=read();r=read();
cout<<Count(r)-Count(l-1)<<endl;
return 0;
}
```
by 渺小的Mastar @ 2019-03-30 09:41:30
可以忽略我的瞎jb注释qwq
by 渺小的Mastar @ 2019-03-30 09:42:05