洛谷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;
}