首页 > 代码库 > bzoj1026windy数

bzoj1026windy数

题目链接: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[11][10];
inline int abs(int x){return x>0?x:-x;}
void init(){
    for (i=1;i<=9;i++)f[1][i]=1;f[1][0]=1;
    for (i=2;i<=11;i++){
        for (j=0;j<=9;j++){
            for (k=0;k<=9;k++)
                if (abs(j-k)>=2)f[i][j]+=f[i-1][k];
        }
    }
}
inline int solve(int x){
    int len=0,a[15],t=x,ans=0;
    while (t)a[++len]=t%10,t/=10;
    for (i=1;i<a[len];i++)ans+=f[len][i];
    for (i=len-1;i>=1;i--)for (j=1;j<=9;j++)ans+=f[i][j];
    for (i=len-1;i>=1;i--){
        for (j=0;j<a[i];j++)
            if (abs(a[i+1]-j)>=2)ans+=f[i][j];
        if (abs(a[i]-a[i+1])<2)break;
    }
    return ans;
}
int main(){
    init();
    scanf("%d%d",&n,&m);
    printf("%d\n",solve(m+1)-solve(n));
    return 0;
}

 

bzoj1026windy数