\(Description:\)

给出a,b，求\([a,b]\)区间满足相邻两位之间差大于等于2的数的个数

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

\(Sample\) \(Input:\)

1 10

\(Sample\) \(Output\)

9

\(Sample\) \(Intput:\)

25 50

\(Sample\) \(Output:\)

20

\(Solution:\)

我天，刚刚入门数位dp就刚题？

喵的，听课的时候持续掉线。。。

我的服务器被屏蔽了吧。。。

回家刻苦学习，经过又是无数次的掉线和重连。。。

好的那么来切一下这道题

发现这题可以数位dp，不会dp，写记忆化

一般数位dp的dfs都传入三个参：

当前在填数字的（len），上一个会对dfs有影响的数（\(pre || last\))，上一位有没有取到要求的边界。

形如:

inline int dfs(int len,int pre,bool limit)

那么为什么要积有没有取到边界呢？

我们考虑比如对于：5123这个范围。

如果最高位取 \(1\) 那么后面第二位可以取 \(1\) ~ \(9\) 任何与上一个差的绝对值大于2的

其他小于等于 \(4\) 的都可以这么取。

但是如果到了 \(5\) 那就不一样了，后面第二位只能取到 \(1\) ，因为不能让范围大于给出的数。

还要考虑前导 \(0\) 的问题，我们可以把 \(0\) 放在首位，但不能对后一个产生那个绝对值问题的影响，那么就要把这个影响消掉，比如如果这位是前导 \(0\) ，那么就把他弄成 \(-10\) ，这样就不会有影响了。

前导 \(0\) ，的确较难处理，较难理解，那就再来个栗子：

比如要求\(a\) ~ \(b\)的数各个位数相同的数有几个，那么 \(111,222,333\) 什么的都算，但如果有一个前导 \(0\)

就凉了。。。他会把 \(0111\) 判作非法。

上代码把：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
int l,r,cnt,ans;
const int N=15;
int f[N][N],digit[N];
inline void solve(int n){
    cnt=0;
    while(n){
        digit[++cnt]=n%10;
        n/=10;
    }
    for(int i=1;i+i<=cnt;++i) swap(digit[i],digit[cnt-i+1]);
}
inline int dfs(int len,int last,bool limit){
    if(len==cnt) return 1;
    if(last>=0 && !limit && f[len][last]!=-1) return f[len][last];
    int ret=0,up_bound=(limit)?digit[len+1]:9;
    for(int i=0;i<=up_bound;++i){
        if(abs(i-last)<2) continue;
        int pre=i;
        if(last==-10 && i==0) pre=last;
        
        ret+=dfs(len+1,pre,limit&&i==digit[len+1]);
    }
    if(last>=0 && ret) f[len][last]=ret;
    return ret;
}
signed main(){
    scanf("%lld%lld",&l,&r);
    memset(f,-1,sizeof(f));
    solve(r);
    ans=dfs(0,-10,true);
    solve(l-1);
    memset(f,-1,sizeof(f));
    printf("%lld\n",ans-dfs(0,-10,true));
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄