问题描述

windy 定义了一种 windy 数。不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道在 A 和 B 之间(包括 A 和 B)总共有多少个 windy 数?

输入

包含两个整数,A B。

输出

一个整数,同题目要求

思路

一个比较简单的数位DP吧,直接按照套路来就好了。$f[i][j]$ 表示在第 $i$ 位上为 $j$ 的可能情况数,利用 $f$ 数组记忆化。然后需要注意的是,处理前导零时也不能够记忆化(仅针对我这种写法)。

代码

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

int l, r, dig[12], f[10][10];

int dp(int x, int lim, int tag, int num)
{
    if(x==0) return tag;
    if(!lim && tag && f[x][num]!=-1) return f[x][num];
    int temp=0;
    if(!tag)
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(i==0) temp+=dp(x-1, lim&&i==dig[x], 0, 0);
            else temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    else
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(abs(num-i)<2) continue;
            temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    if(!lim && tag) f[x][num]=temp;
    return temp;
}

int solve(int x)
{
    int cnt=0;
    memset(f, -1, sizeof(f));
    while(x) dig[++cnt]=x%10, x/=10;
    return dp(cnt, 1, 0, 0);
}

int main()
{
    scanf("%d%d%", &l, &r);
    //printf("%d %d!!!\n", solve(r), solve(l-1));
    printf("%d\n", solve(r)-solve(l-1));
}

发表评论

邮箱地址不会被公开。 必填项已用*标注