[CDOJ 250] windy 수.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int dp[11][10];

void Init()
{
    memset(dp,0,sizeof(dp));
    int i,j,k;
    for(i = 0; i <= 9; ++i) dp[1][i]++;

    for(i = 2; i <= 10; ++i)
        for(j = 0; j <= 9; ++j)
            for(k = 0; k <= 9; ++k)
                if(abs(j-k) >= 2) dp[i][j] += dp[i-1][k];
}

int Solve(int n)
{
    int ans = 0,len = 0,bit[12],i,j;
    while(n)
    {
        bit[++len] = n%10;
        n /= 10;
    }

    for(i = len-1; i; --i)//1~len-1      
        for(j = 1; j <= 9; ++j)
            ans += dp[i][j];

    for(i = 1; i < bit[len]; ++i)//len <          
        ans += dp[len][i];

    for(i = len-1; i; --i)// ->   
    {
        for(j = 0; j < bit[i]; ++j)
            if(abs(j-bit[i+1]) >= 2)
                ans += dp[i][j];

        if(abs(bit[i]-bit[i+1])<2)//          
            break;
    }
    return ans;
}

int main()
{
    int i,j;
    Init();
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        printf("%d
",Solve(b+1)-Solve(a));
    }
    return 0;
}

//   
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int dp[10][2][10];
int digit[10];

/* pre     0~9 hs   0 */

int dfs(int pos,int pre,int hs,bool high)
{
    if(pos == -1) return !hs || pre;
    if(!high && ~dp[pos][hs][pre]) return dp[pos][hs][pre];

    int i,en,ans = 0;
    en = high? digit[pos]: 9;

    for(i = 0; i <= en; ++i)
    {
        if(!hs && abs(i-pre) < 2) continue;
        ans += dfs(pos-1,i,hs && !i,high && i == en);
    }

   if(!high) dp[pos][hs][pre] = ans;
    return ans;
}

int Solve(int x)
{
    int len = 0;
    while(x)
    {
        digit[len++] = x%10;
        x /= 10;
    }
    return dfs(len-1,0,1,1);
}

int main()
{
    int a,b;
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&a,&b);
    printf("%d
",Solve(b)-Solve(a-1));
    return 0;
}