洛谷P2657 [SCOI2009] windy 数 题解

题目链接：P2657 [SCOI2009] windy 数

题意：

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$。

常规的数位dp，只需要记录上一位的数字即可

但是注意，最高位是不需要限制的

具体的，我们是从高位往低位做dp的

至于为什么高位往低位做dp，可以看下面的解释

因为低位开始会导致无法判断是否超过了当前的限制

例如 $4234$ ，假设我们从高位开始做

如果以 $4$ 开始，可以发现接下来一位不能超过 $3$

如果用 $0 \sim 3$ ，则接下来没有任何限制

但是如果我们从低位开始做，比如填了一个 $8$

那么最后我们有可能推出来个 $4238$ 之类的

因为无法判断

回到刚刚的问题，我们从高位往低位做数位dp

那么第一位，也就是我们推的某个数的最高位，

是可以随便填而不受到大于 $2$ 那个限制的（即前导零不能限制实际的最高位选择）

因此我们还需要记录是否之前全是 $0$

复杂度不太清楚，不过应该和位数有关，这题的位数就十几，所以基本上是 $O(1)$ 的

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int n,a[15],num[15],f[15][15];
int dfs(int u,int pre,int st,int limit)
{
    if(!u) return 1;
    if(!limit&&f[u][pre]!=-1)
        return f[u][pre];
    int up=limit?num[u]:9,ans=0;
    for(int i=0; i<=up; i++)
    {
        if(abs(i-pre)<2) continue;
        if(st&&!i) ans+=dfs(u-1,-2,1,limit&&num[u]==i);
        else ans+=dfs(u-1,i,0,limit&&num[u]==i);
    }
    if(!limit&&!st) f[u][pre]=ans;
    return ans;
}
int solve(int x)
{
    int len=0;
    while(x>0)
    {
        num[++len]=x%10;
        x/=10;
    }
    return dfs(len,-2,1,1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,-1,sizeof(f));
    int l,r; cin >> l >> r;
    cout << solve(r)-solve(l-1) << '\n';
    return 0;
}