[bzoj 1026] [SCOI2009]windy数：数位DP

题意：区间[a, b]里有多少个不含前导0的十进制整数任意相邻两位之差的绝对值不小于2？（1<=a<=b<=2,000,000,000，a, b是整数）

前几天做XJOI模拟赛中有关字典序的一道题，发现可以按照某种顺序从高位向低位统计。十进制数之间的比较，把前导0补齐，实际上就是字符串的比较。

举例，如果允许前导0，小于34023的自然数可以这样生成（下划线表示0~9间任意数码）：
0 _ _ _ _
1 _ _ _ _
2 _ _ _ _
3 0 _ _ _
3 1 _ _ _
3 2 _ _ _
3 3 _ _ _
3 4 0 0 _
3 4 0 1 _
3 4 0 2 0
3 4 0 2 1
3 4 0 2 2

有了这个背景，回到本题。显然，我们可以统计[1, b+1)和[1, a)内的结果，再作差。预处理，设f[i][j]为长度为(i+1)位十进制串（允许前导0）中有多少个符合“任意相邻两位之差的绝对值不小于2”。统计[1, x)内的结果时，先统计位数小于x的，再统计最高位小于x的，然后按照上面所述顺序，统计高k位与x相同的，如果x的高k位已不符合Windy数的定义，须及时退出。

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAX_N = 10;
int f[MAX_N][10], g[MAX_N];

int cal(char* s, int n)
{
    int ans = n > 1 ? g[n-2] : 0;
    for (int i = 1; i < s[0]-'0'; ++i) // 最高位
        ans += f[n-1][i];
    for (int i = 1; i < n; ++i) { // s[0..i)相同
        int c2 = s[i-1] - '0', c1 = s[i] - '0';
        for (int j = 0; j < c1; ++j)
            if (abs(j-c2) >= 2)
                ans += f[n-i-1][j];
        if (abs(c2-c1) < 2)
            break;
    }
    return ans;
}

int main()
{
    char sa[11], sb[11];
    int a, b;
    scanf("%d %d", &a, &b);
    ++b;
    int la = sprintf(sa, "%d", a), lb = sprintf(sb, "%d", b);

    for (int i = 0; i < 10; ++i)
        f[0][i] = 1;
    for (int i = 1; i < lb; ++i)
        for (int j = 0; j < 10; ++j)
            for (int k = 0; k < 10; ++k)
                if (abs(k-j) >= 2)
                    f[i][j] += f[i-1][k];
    g[0] = 9;
    for (int i = 1; i < lb; ++i) {
        g[i] = g[i-1];
        for (int j = 1; j < 10; ++j)
            g[i] += f[i][j];
    }

    printf("%d\n", cal(sb, lb) - cal(sa, la));

    return 0;
}