题目大意

不含前导零且相邻两个数字之差至少为$2$的正整数被称为$windy$数

询问在$A$和$B$之间，包括$A$和$B$，总共有多少个$windy$数

数据范围

$1\leqslant A\leqslant B\leqslant 2\times 10^9$

题解

$opt[i][j]$表示当有一个数有$i$位数，最高位为$j$的$windy$数的个数

$opt[i][j]+=opt[i-1][k](0\leqslant k\leqslant 9\ and\ |j-k|\geqslant 2)$

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
#define inf 0x3f3f3f3f

using namespace std;

ll opt[15][15];
int digit[15],len;
ll l,r,sum;

inline void init(){
    scanf("%lld%lld",&l,&r);
    For(i,0,9) opt[1][i]=1;
    For(i,2,10)
        For(j,0,9)
            For(k,0,9)
                if (abs(j-k)>=2) opt[i][j]+=opt[i-1][k];
}

inline ll get(ll x){
    if (!x) return 0;
    len=0,sum=0;memset(digit,0,sizeof(digit));
    while(x) {digit[++len]=x%10;x/=10;}
    For(i,1,len-1)
        For(j,1,9) sum+=opt[i][j];
    For(i,1,digit[len]-1) sum+=opt[len][i];
    for(int i=len-1;i>=1;i--){
        For(j,0,digit[i]-1)
            if (abs(digit[i+1]-j)>=2) sum+=opt[i][j];
        if (abs(digit[i+1]-digit[i])<2) break;
    }
    return sum;
}

int main(){
    init();
    printf("%lld\n",get(r+1)-get(l));
    return 0;
}