bzoj1026windy数

2022-07-27 11:40:45

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

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第一题，调了一天。。。。。

题解：

数位DP，f[i][j]代表长度为i，首尾是j的windy数个数。

然后先简单的预处理出来f数组。

然后呢？

假设现要求的数为ABCD，那么，我们可以先算出不含ABCD这四个数字与位置对应的数个数（即A不在千位，B不在百位，以此类推）。

then，再算出一一包含的数的个数（即A在千位，B在百位，以此类推）。

若相邻两位只差<2，就break。

对了，solve(m)重并没有计算m，所以m要加1.

然后，solve(x)算出了1~x-1的windy数的个数，只要solve(m+1)-solve(n)就行了。

代码

#include <cstdio>

using namespace std;

int i,j,k,n,m,f[][];

inline int abs(int x){return x>?x:-x;}

void init(){

    for (i=;i<=;i++)f[][i]=;f[][]=;

    for (i=;i<=;i++){

        for (j=;j<=;j++){

            for (k=;k<=;k++)

                if (abs(j-k)>=)f[i][j]+=f[i-][k];

        }

    }

}

inline int solve(int x){

    int len=,a[],t=x,ans=;

    while (t)a[++len]=t%,t/=;

    for (i=;i<a[len];i++)ans+=f[len][i];

    for (i=len-;i>=;i--)for (j=;j<=;j++)ans+=f[i][j];

    for (i=len-;i>=;i--){

        for (j=;j<a[i];j++)

            if (abs(a[i+]-j)>=)ans+=f[i][j];

        if (abs(a[i]-a[i+])<)break;

    }

    return ans;

}

int main(){

    init();

    scanf("%d%d",&n,&m);

    printf("%d\n",solve(m+)-solve(n));

    return ;

}

码农公寓