题目描述

注释版，仅记录。

算法1

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
#include<cmath>
using namespace std;

const int N=11;

//前导零队windy数的性质产生影响，不能随意加

int f[N][10];       //f[i][j]表示i位最高为是j的windy数个数。

void init()
{
    for(int i=0;i<=9;i++) f[1][i]=1;

    for(int i=2;i<N;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(abs(j-k)>=2)
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }
    }
}

int dp(int n)
{
    if(!n) return 0;

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

    int res=0;
    int last=-3;
    for(int i=nums.size()-1;i>=0;i--)   //这里只处理了没有前导0的情况
    {
        int x=nums[i];
        for(int j = i==nums.size()-1;j<x;j++)   //根据是否是最高位从0或者1开始枚举
        {
            if(abs(j-last)>=2)
                res+=f[i+1][j];
        }

        if(abs(x-last)>=2) last=x;
        else break;

        if(!i) res++;
    }

    //特殊枚举有前导零的数
    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;
}