原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

题解：

这是个很水的数位dp，令dp[i][j]表示总共i位，第i位是j的方案数。转移就是dp[i][j]+=dp[i-1][k]，其中abs(j-k)>=2。然后统计答案的时候瞎比搞搞就好。

代码：

/**************************************************************    Problem: 1026    User: HarryGuo2012    Language: C++    Result: Accepted    Time:0 ms    Memory:1280 kb****************************************************************/ #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define MAX_N 100using namespace std; string A,B; typedef long long ll; ll dp[MAX_N][10]; ll work(string s) {    memset(dp, 0, sizeof(dp));    reverse(s.begin(), s.end());    int n = s.length();    for (int i = 0; i < 10; i++)dp[0][i] = 1;    for (int i = 1; i < n; i++)        for (int j = 0; j < 10; j++) {            for (int k = 0; k <= j - 2; k++)                dp[i][j] += dp[i - 1][k];            for (int k = j + 2; k <= 9; k++)                dp[i][j] += dp[i - 1][k];        }    ll ans = 0;    for (int i = 0; i < n - 1; i++)        for (int j = 1; j <= 9; j++)ans += dp[i][j];    for (int i = n - 1; i >= 0; i--) {        for (int j = (i == n - 1); j < s[i] - '0'; j++) {            if ((i != n - 1) && abs(j - s[i + 1] + '0') < 2)continue;            ans += dp[i][j];        }        if ((i != n - 1) && abs(s[i] - s[i + 1]) < 2)break;    }    return ans;} bool check(string s){    for(int i=1;i
          
           <2)return false; return true;} int main() { cin >> A >> B; cout << work(B) - work(A) + (check(A) && check(B)) << endl; return 0;}