【数位Dp】windy数

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

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

【输入格式】

　　包含两个整数，A B。

【输出格式】

　　一个整数

【输入样例一】

1 10

【输出样例一】

9

【输入样例二】

25 50

【输出样例二】

20

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

思路

这题其实就是一道数位Dp裸题

定义一个四维数组分别表示走到第几位，这位是什么，是否压线，是否有前导零

然后从高位开始倒着循环每一位

f数组记录的是在这一位上，数是j，是否压线，是否前导零，的数有多少个

最后求一下和

注：在处理前面的区间时，不要减去压线的情况

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int f[][][][];
int a[],an,n,m;
inline void fj(int x){
    an=;
    while(x>){
        a[++an]=x%;
        x/=;
    }
}
inline void df(){
    memset(f,,sizeof(f));
    f[an+][][][]=;
    for(int i=an;i>=;--i){
        for(int j=;j<=;++j){
            for(int p=;p<=;++p){
                int pp=;
                if(p==&&j>a[i])continue;
                if(p==&&j==a[i])pp=;
                for(int q=;q<=;++q){
                    for(int k=;k<=;++k){
                        if(q==&&k!=)break;
                        int qq=;
                        if(q==&&j==)qq=;
                        if(abs(j-k)>=||q)
                        f[i][j][pp][qq]+=f[i+][k][p][q];
                    }
                }
            }
        }
    }
}
long long ans=;
int main()
{
    scanf("%d%d",&m,&n);
    fj(n);df();
    for(int i=;i<=;++i)
    ans+=f[][i][][]+f[][i][][]+f[][i][][]+f[][i][][];
    fj(m);df();
    for(int i=;i<=;++i)
    ans-=f[][i][][]+f[][i][][];
    printf("%lld",ans);
    return ;
}