P13085 [SCOI2009] windy 数（加强版）
大意
不含前导零且相邻两个数字之差至少为 \(2\) 的正整数被称为 windy 数。windy 想知道，在 \(a\) 和 \(b\) 之间，包括 \(a\) 和 \(b\)，总共有多少个 windy 数？
思路
首先，我们考虑数位 DP，那么设状态 \(f[pos][st][lim][zero]\) 来表示在 pos 的位置，上一个位置的值为 st，当前填的数字是否受限制，是否处于前导零状态的答案。
那么我们就要考虑转移的过程，首先，如果当前的是前导 \(0\) 状态，拿就直接往后就行了，如果不是的话就要考虑差值要 \(\ge 2\)，如果满足条件，就继续往后搜索。
查询的时候前缀和一下，做差就好。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;#define ll long longconst int MAXN = 20;
int len = 0;
int a[MAXN];
ll f[MAXN][10][2][2];
//pos st lim zeroll dp(int pos, int st, bool lim, bool zero){if(pos == len){return 1ll;}if(~f[pos][st][lim][zero]){return f[pos][st][lim][zero];}ll ans = 0;int maxx = lim ? a[pos] : 9;for(int i = 0;i <= maxx;i ++){int nw = (i == 0) && zero;if(nw){ans += dp(pos + 1, 0, lim && (i == maxx), nw);}else if(zero || abs(i - st) >= 2){ans += dp(pos + 1, i, lim && (i == maxx), nw);}}return f[pos][st][lim][zero] = ans;
}ll solve(ll x){memset(f, -1, sizeof(f));len = 0;while(x){a[len ++] = x % 10;x /= 10;}reverse(a, a + len);return dp(0, 0, 1, 1);
}int main(){ll L, R;cin >> L >> R;cout << solve(R) - solve(L - 1) << '\n';return 0;
}