[bzoj1026][SCOI2009][windy数] (数位dp)

时间:2020-12-22 20:40:40

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 。

Solution

#include<math.h>
#include<stdio.h>
int a,b,f[12][12],len,zt[12];
void init() {
    for(int j=0; j<10; j++)
        f[1][j]=1;
    for(int i=2; i<=10; 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]; }
int getans(int x) {
    for(len=0; x; x/=10)
        zt[++len]=x%10;
    int res=0;
    for(int i=1; i<len; i++)
        for(int j=1; j<10; j++)
            res+=f[i][j];
    for(int j=1; j<zt[len]; j++)
        res+=f[len][j];
    for(int i=len-1; i; i--) {
        if(i==1 && abs(zt[i+1]-zt[i])>=2)res++;
        for(int j=0; j<zt[i]; j++)
            if(abs(zt[i+1]-j)>=2)
                res+=f[i][j];
        if(abs(zt[i+1]-zt[i])<2)break; }
    return res; }
int main() {
    init();
    scanf("%d%d",&a,&b);
    printf("%d\n",getans(b)-getans(a-1));
    return 0; }