UESTC1307 windy数数位DP

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

dp[i][j],代表j开头的i位数字，跟前面几道差不多，然后枚举递推各个数位上数字关系，感觉比前面做的还简单，大差不差，因为没有前导0，所以从高位开始搞起比较方便

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int dp[100 + 5][100 + 5]; int sum[100 + 5]; int num[100 + 5]; void init() { int i,j,k; for(i=0;i<10;i++) dp[i][1] = dp[i][0] = 1; sum[1] = 10; for(j=2;j<=10;j++) { sum[j] = sum[j - 1]; for(i=0;i<10;i++) { for(k=0;k<10;k++) if(abs(i - k) > 1) dp[i][j] += dp[k][j - 1]; if(i) sum[j] += dp[i][j]; } } } int cal(int x) { memset(num,0,sizeof(num)); if(x == 0) return 0; if(x < 10) return x; int cnt = 0; while(x) { num[cnt++] = x%10; x /= 10; } for(int i=0;i
                    
                      1) ans += dp[j][cnt - i]; } else if(i) { for(int j=0;j
                     
                       1) ans += dp[j][cnt - i]; if(abs(num[i] - num[i-1]) < 2) return ans - 1; } else { ans = sum[cnt - 1]; for(int j=1;j

UESTC1307 windy数 数位DP