AcWing 1083. Windy数

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

Windy 想知道，在 A和 B之间，包括 A和 B，总共有多少个 Windy 数？

输入格式
共一行，包含两个整数 A和 B。

输出格式
输出一个整数，表示答案。

数据范围
1≤A≤B≤2×10^9

1 10


9


25 50


20

#include<bits/stdc++.h>

using namespace std;

const int N = 11;

int f[N][N];//一共i位数 最高位是j 

//预处理
void init()
{
    for(int i=0;i<=9;i++) f[1][i]=1;//特判个位数为windy数 

    for(int i=2;i<N;i++)//i位数 
        for(int j=0;j<=9;j++)//枚举最高位 j 
            for(int k=0;k<=9;k++)//遍历0-9 
                if(abs(j-k)>=2)//合法情况 
                    f[i][j]+=f[i-1][k];
}

// 0 ～ n 中 windy 数的个数
int dp(int n)
{
    if(!n) return 0;

    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n/=10;
    }

    //处理 nums.size() 位数的windy数的个数
    int res=0,last=-2;//last开局任取与0-9 差距绝对值大于2的数（=-2 
    for(int i=nums.size()-1;i>=0;i--)//从高到低 枚举每个数位上的数 
    {
        int x=nums[i];
        //左子树 
        //小巧思 当 i==nums.size()成立时，j从1开始
        //反之j从0开始 
        for(int j=i==nums.size()-1;j<x;j++)
            if(abs(j-last)>=2)
                res+=f[i+1][j];

        //右子树不符合情况时（自己） 
        if(abs(x-last)<2) break;

        last=x;

        if(!i) res++;
    }

    //处理小于 nums.size() 位数的windy数的个数（前面计算不包括 前导0 
    for(int i=1;i<nums.size();i++)
        for(int j=1;j<=9;j++)
            res+=f[i][j];

    return res;
}

int main()
{
    init();

    int l,r;

    cin>>l>>r;

    cout<<dp(r)-dp(l-1)<<endl;

    return 0;
}