【bzoj1026】windy数

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6214 Solved: 2773
[Submit][Status][Discuss]

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

【题解】

这题类似于hdu2089，但是这题不能出现前导零，注意处理这点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<algorithm>
 8 using namespace std;
 9 int f[11][11],digit[11];
10 inline int read()
11 {
12     int x=0,f=1;  char ch=getchar();
13     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
14     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
15     return x*f;
16 }
17 void pre()
18 {
19     for(int i=0;i<=9;i++)  f[1][i]=1;
20     for(int i=2;i<=10;i++)
21         for(int j=0;j<=9;j++)
22             for(int k=0;k<=9;k++)
23                 if(abs(j-k)>=2)  f[i][j]+=f[i-1][k];
24 }
25 int ask(int x)
26 {
27     int len=0,ans=0;
28     while(x)  {digit[++len]=x%10; x/=10;}
29     for(int i=1;i<len;i++)
30         for(int j=1;j<=9;j++)
31             ans+=f[i][j];
32     for(int i=1;i<digit[len];i++)  ans+=f[len][i];
33     for(int i=len-1;i;i--)
34     {
35         for(int j=0;j<digit[i];j++)  if(abs(j-digit[i+1])>=2)  ans+=f[i][j];
36         if(abs(digit[i]-digit[i+1])<2)  break;
37     }
38     return ans;
39 }
40 int main()
41 {
42     //freopen("cin.in","r",stdin);
43     //freopen("cout.out","w",stdout);
44     int l=read(),r=read();
45     pre();
46     printf("%d
",ask(r+1)-ask(l));
47     return 0;
48 }