BZOJ-1026: [SCOI2009]windy数

Description

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？1<=A<=B<=2000000000

数位DP。
也不是很繁琐的样子。
dp[i][j]表示以j数码开头的i位数中windy数的个数。
统计答案分两部分：1.统计不含x前缀的部分2.含有x前缀的部分。统计前缀答案相减。好像区间端点+1会简单点

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[12][10],L,R;
inline int Abs(int x){return x>0?x:-x;}
int getans(int x)
{
    int re=0,top=0; static int z[12];
    while(x) z[++top]=x%10,x/=10;
    for(int i=1;i<z[top];++i) re+=dp[top][i];
    for(int i=1;i<top;++i) for(int k=1;k<=9;++k) re+=dp[i][k];
    for(int i=top-1;i;--i)
    {
        for(int j=0;j<z[i];++j)
            if(Abs(z[i+1]-j)>=2) re+=dp[i][j];
        if(Abs(z[i+1]-z[i])<2) break;
    }
    return re;
}
int main()
{
    scanf("%d%d",&L,&R);
    for(int i=0;i<=9;++i) dp[1][i]=1;
    for(int i=2;i<=10;++i)
        for(int j=0;j<=9;++j)
            for(int k=0;k<=9;++k)
                if((Abs(k-j)>=2)) dp[i][j]+=dp[i-1][k];
    printf("%d\n",getans(R+1)-getans(L));
    return 0;
}