题目大意：在A和B之间，包括A和B，总共有多少个不含前导零且相邻两个数字之差至少为2的正整数？
显然是数位dp啦=w=。
显然与上一位有关，我们$dfs$的时候就要记录$pre$。因为这是有前导零，所以我们需要分类讨论。
当$ling==1&&i==0$，当前位还是前导零，那么我们之前放什么即可。为了放什么即可，我们开始可以设成-2.这样与谁的绝对值都会大于等于2了。（脆角！）
否则的话按部就班放当前位就行了。
Code
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 typedef long long ll; 7 8 int len; 9 int border[20]; 10 ll dp[20][13]; 11 ll a,b,ans1,ans2; 12 13 ll dfs(int pos,int pre,int ling,int limit) 14 { 15 if(pos<1) return 1; 16 if(!limit&&dp[pos][pre]!=-1&&!ling) return dp[pos][pre]; 17 ll tmp=0; 18 ll lim=limit ? border[pos] : 9 ; 19 for(int i=0;i<=lim;i++) 20 { 21 if(abs(i-pre)<2) continue; 22 if(i==0&&ling) tmp+=dfs(pos-1,-2,1,(limit&&i==lim)); 23 else tmp+=dfs(pos-1,i,0,(limit&&i==lim)); 24 } 25 if(!limit&&!ling) dp[pos][pre]=tmp; 26 return tmp; 27 } 28 29 int main() 30 { 31 scanf("%lld%lld",&a,&b); 32 a--; 33 memset(dp,-1,sizeof(dp)); 34 while(a) 35 { 36 border[++len]=a%10; 37 a/=10; 38 } 39 ans1=dfs(len,-2,1,1); 40 len=0; 41 memset(dp,-1,sizeof(dp)); 42 while(b) 43 { 44 border[++len]=b%10; 45 b/=10; 46 } 47 ans2=dfs(len,-2,1,1); 48 printf("%lld ",ans2-ans1); 49 return 0; 50 }