【數位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 ;
}