bzoj1026 windy数（数位DP）

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。

#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<algorithm>
#ifdef WIN32
#define ll "%I64d"
#else
#define ll "%lld"
#endif
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
typedef long long LL;
inline LL read(){
    LL x=0;char ch=getchar();bool f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f?x:-x;
}
LL base[15],dp[15][15];
LL query(int x){
    if(!x)return 0;
    int w=10;while(base[w]>x)w--;
    LL ans=0;
    rep(i,1,w-1)rep(j,1,9)ans+=dp[i][j];
    int now=x/base[w];
    rep(i,1,now-1)ans+=dp[w][i];
    x%=base[w];int pre=now;
    dep(i,w-1,1){
        now=x/base[i];
        if(i==1)now++;
        rep(j,0,now-1)if(abs(pre-j)>=2)ans+=dp[i][j];
        if(abs(pre-now)<2)break;
        pre=now;x%=base[i];
    }
    return ans;
    
}
int main(){
    base[1]=1;rep(i,2,10)base[i]=base[i-1]*10;
    rep(i,0,9)dp[1][i]=1;
    rep(i,2,10)rep(j,0,9)rep(k,0,9)if(abs(j-k)>=2)dp[i][j]+=dp[i-1][k];
    LL l=read(),r=read();
    printf("%lld\n",query(r)-query(l-1));
    return 0;
}

秒客网