[BZOJ1026] [SCOI2009] windy數 (數位dp)

Description

　　windy定義了一種windy數。不含前導零且相鄰兩個數字之差至少為2的正整數被稱為windy數。 windy想知道，在A和B之間，包括A和B，總共有多少個windy數？

Input

　　包含兩個整數，A B。

Output

　　一個整數

Sample Input

　　【輸入樣例一】
1 10
　　【輸入樣例二】
25 50

Sample Output

　　【輸出樣例一】
9
　　【輸出樣例二】
20

HINT

　　【數據規模和約定】
　　100%的數據，滿足 1 <= A <= B <= 2000000000 。

Source

Solution

　　設$f[i][j]$表示i位數且最高位為j的滿足題意的數有多少個:

　　$f[i][j] = \sum\limits_{|k - j| \geq {2}}^{9}f[i - 1][k]$

　　查詢時按照類前綴和的原理進行。

#include <bits/stdc++.h>
using namespace std;
int num[11], f[11][10];
 
int solve(int x)
{
    int len, ans = 0;
    for(len = 0; x; x /= 10)
        num[len++] = x % 10;
    for(int i = 0; i < len - 1; i++)
        for(int j = 1; j < 10; j++)
            ans += f[i][j];
    for(int i = 1; i < num[len - 1]; i++)
        ans += f[len - 1][i];
    for(int i = len - 2; i > -1; i--)
    {
        for(int j = 0; j < num[i]; j++)
            if(abs(j - num[i + 1]) >= 2) ans += f[i][j];
        if(abs(num[i] - num[i + 1]) < 2) break;
    }
    return ans;
}
 
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    for(int i = 0; i < 10; i++)
        f[0][i] = 1;
    for(int i = 1; i < 11; i++)
        for(int j = 0; j < 10; j++)
            for(int k = 0; k < 10; k++)
                if(abs(j - k) >= 2) f[i][j] += f[i - 1][k];
    cout << solve(b + 1) - solve(a) << endl;
    return 0;
}