UESTC 250

windy数

基本的数位DP，需要判断当前位是否为起始位。

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

#define D(x) x

const int MAX_DIGIT = 35;

int n, m;
int f[MAX_DIGIT];
int memoize[MAX_DIGIT][2][2][15];

void to_digits(int a)
{
    for (int i = 0; i < MAX_DIGIT; i++)
    {
        f[i] = a % 10;
        a /= 10;
    }
}

int dfs(int digit, bool less, bool first, int last)
{
    if (digit == -1)
    {
        return 1;
    }
    if (memoize[digit][less][first][last] != -1)
    {
        return memoize[digit][less][first][last];
    }
    int limit = less ? 9 : f[digit];
    int ret = 0;
    for (int i = 0; i <= limit; i++)
    {
        if (!first && abs(i - last) < 2)
        {
            continue;
        }
        ret += dfs(digit - 1, less || i < f[digit], first && i == 0, i);
    }
    memoize[digit][less][first][last] = ret;
    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);
    n--;
    to_digits(n);
    memset(memoize, -1, sizeof(memoize));
    int ans_n = dfs(32, false, true, 12);
    to_digits(m);
    memset(memoize, -1, sizeof(memoize));
    int ans_m = dfs(32, false, true, 12);
    printf("%d
", ans_m - ans_n);
    return 0;
}