[SCOI2009] windy 数

#include <bits/stdc++.h>
using namespace std;
long long n, m;
int len, d[20];
long long dp[20][10];
//pre、iszero：避开差为2的限制
//limit：当前位能否为0~9，如果limit为真，表示当前位最多只能是d[pos]
long long dfs(int pos, int pre, bool iszero, bool limit)
{
    if (pos == 0)
        return 1;
    if (!iszero && !limit && dp[pos][pre] != -1)
        return dp[pos][pre];
    int maxD = limit ? d[pos] : 9;
    long long ans = 0;
    for (int now = 0; now <= maxD; now++)
    {
        if (iszero)
            ans += dfs(pos - 1, now, iszero && now == 0, limit && now == d[pos]);
        else
        {
            if (abs(now - pre) < 2)
                continue;
            ans += dfs(pos - 1, now, iszero && now == 0, limit && now == d[pos]);
        }
    }
    if (!iszero && !limit)
        dp[pos][pre] = ans;
    return ans;
}
long long cal(long long x)
{
    len = 0;
    while (x > 0)
        d[++len] = x % 10, x /= 10;
    memset(dp, -1, sizeof(dp));
    return dfs(len, 0, true, true);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    cout << cal(m) - cal(n - 1) << endl;
    return 0;
}