BZOJ-1026: [SCOI2009]windy数 (数位DP)-白红宇

BZOJ-1026: [SCOI2009]windy数 (数位DP)

阅读量：5054 次

发布时间：2019-06-12

本文共 1337 字，大约阅读时间需要 4 分钟。

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB

Submit: 5665 Solved: 2534

[][][]

Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】

1 10

【输入样例二】

25 50

Sample Output

【输出样例一】

【输出样例二】

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

Source

算法：比较基础的数位DP，详细解释程序中有

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include "algorithm"10 using namespace std;11 typedef long long LL;12 const int MAX=15;13 int f[MAX][10];14 //f[i][j] 表示 i 位数，最高位为 j 的方案数 15 16 void init(){ //初始化范围内的所有数 17 int i,j,k;18 memset(f,0,sizeof(f));19 for (i=0;i<10;i++)20 f[1][i]=1;21 for (i=2;i
             
              =2)//符合条件 25 f[i][j]+=f[i-1][k];26 }27 int satistics(int x){28 int ans(0);29 int s[MAX]={ 0};30 while (x) {s[++s[0]]=x%10;x/=10;}//数字分离 31 s[s[0]+1]=0;32 int i,j,k;33 for (i=1;i
              
               =1;i--)40 { for (j=0;j
               
                =2)42 ans+=f[i][j];43 if (abs(s[i]-s[i+1])<2)//如果已经出现不合法的，那么就直接退出 44 break;45 }46 return ans;47 }48 int main(){49 init();int i,j;50 int x,y;51 scanf("%d%d",&x,&y);52 printf("%d",satistics(y+1)-satistics(x));53 return 0;54 }