数位 DP 题目。

说起来数位 DP 是不是都这么设计状态啊 …… 积累好贫乏有人教教我吗 ……

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;long long l, r, len, a[12], dp[12][12], ans; // 搜到第 i 位，上一位为 j (j != limit_num) 的方案数inline long long Abs(long long x) { return x > 0 ? x : -x; }inline long long Deep_fs(int pos, int pre, int firs, int limit) { // 当前位置，前一位数，前面是否全是零，是否为最高位限制 if( pos > len ) return 1; if( limit == 0 && dp[pos][pre] != -1 ) return dp[pos][pre]; long long res = 0, tmp = limit ? a[len - pos + 1] : 9; for(int i = 0; i <= tmp; ++i) if( Abs(i - pre) > 1 ) { if( firs && i == 0 ) res = res + Deep_fs(pos + 1, -2, 1, limit && i == tmp); else res = res + Deep_fs(pos + 1, i, 0, limit && i == tmp); } if( limit == 0 && firs == 0 ) dp[pos][pre] = res; return res;}inline long long Slove(long long x) { len = 0, memset(dp, -1, sizeof dp); while( x ) a[++len] = x % 10, x = x / 10; return Deep_fs(1, -2, 1, 1);}int main(int argc, char const *argv[]){ scanf("%lld%lld", &l, &r), printf("%d\n", Slove(r) - Slove(l - 1)); return 0;}