BZOJ 1026 [SCOI2009]windy數

1026: [SCOI2009]windy數

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 。

---

　　數位DP，統計類問題。上下界均在int范圍內，故不必用long long（這樣的判斷是很有必要的）。

　　包括A，B。我們通常可以方便算出1~n-1的范圍內符合條件的總數。所以，只需要1~(A+1)-1減去1~B-1即可。

　　DP方程很好寫，但統計確實需要分段。本人最開始想少做些事情，但JIJI了（否則極復雜），也算是刷新了對數位DP的理解。

• 1~9，10~99，100~999，1000~9999……（先把位數為1至cnt-1計入）
• 100..0~(x-1)99..9（確定最高位?）
• x00..0~x(y-1)9..9，xy0..0~xy(z-1)9..9，……，（高位到低位，如果高位已經出現非法，直接退出）

/**************************************************************
    Problem: 1026
    User: Doggu
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
const int N = 15;
int a, b, f[N][10], ans;
int abs(int a) {return a>0?a:-a;}
int DP(int k,int i) { 
    if(f[k][i]) return f[k][i];
    if(k==1) return  f[k][i]=1;
    for( int j = 0; j <= 9; j++ ) if(abs(i-j)>=2) f[k][i]+=DP(k-1,j);
    return f[k][i];
}
void CAL(int num,int delta) {//cal 0~num-1
    int digit[N], cnt = 0;
    while(num) digit[++cnt]=num%10,num/=10;
    for( int bit = 1; bit < cnt; bit++ )  //先把長度為1至cnt-1計入  
        for( int i = 1; i < 10; i++ )
            ans += delta*DP(bit,i);
    for( int i = 1; i < digit[cnt]; i++ )   //確定最高位  
        ans += delta*DP(cnt,i);
    for( int bit = cnt-1; bit >= 1; bit-- ) {
        for( int i = 0; i < digit[bit]; i++ ) if(bit==cnt||abs(i-digit[bit+1])>=2) ans += delta*DP(bit,i);
        if(abs(digit[bit]-digit[bit+1])<2) break;//如果高位已經出現非法，直接退出
    }
}
int main() {
    scanf( "%d%d", &a, &b );
    CAL(b+1,+1);
    CAL(a,-1);
    printf("%d\n",ans);
    return 0;