題目描述

windy定義了一種windy數。不含前導零且相鄰兩個數字之差至少為2的正整數被稱為windy數。 windy想知道，在A和B之間，包括A和B，總共有多少個windy數？

輸入

包含兩個整數，A B。

輸出

一個整數，表示答案

樣例輸入

【輸入樣例一】
1 10
【輸入樣例二】
25 50

樣例輸出

【輸出樣例一】
9
【輸出樣例二】
20

---

題解

數位dp

快聯賽了重寫了一下，發現以前寫的太傻逼了= =

由于加一個數位的貢獻只與最高位有關，因此設 $f[i][j]$ 表示 $i$ 位數，最高位為 $j$ 的數的個數。

那么顯然可以得到 $f[i][j]=\sum\limits_{|j-k|\le 2}f[i-1][k]$ 。

預處理出 $f$ 數組后即可進行數位dp。

先把位數不滿的算上，然后再從高位到低位把該位不滿的加入答案中。

此時需要記錄上一個數位是什么，在枚舉當前數位時需要滿足當前位的條件。并且如果上一個與當前數位產生沖突則不再有滿足條件的數，應當跳出循環。

把詢問區間轉化為 $[1,n)$ 的半開半閉區間更容易處理一些。

代碼中為了避免一些細節（比如最高位只能處理到 $2*10^9$ 之類的），開了long long。

#include <cstdio> typedef long long ll; ll f[11][10] , b[11]; inline int abs(int x) {return x > 0 ? x : -x; } void init() {int i , j , k;b[0] = 1 , b[1] = 10;for(i = 0 ; i < 10 ; i ++ ) f[1][i] = 1;for(i = 2 ; i < 11 ; i ++ ){b[i] = b[i - 1] * 10;for(j = 0 ; j < 10 ; j ++ )for(k = 0 ; k < 10 ; k ++ )if(abs(j - k) >= 2)f[i][j] += f[i - 1][k];} } ll calc(ll n) {int i , j , last = -1 , di = 1;ll ans = 0;for(i = 1 ; b[i] <= n ; i ++ )for(j = 1 ; j < 10 ; j ++ )ans += f[i][j];for( ; i ; i -- ){for(j = di ; j < n / b[i - 1] % 10 ; j ++ )if(abs(j - last) >= 2)ans += f[i][j];if(abs(n / b[i - 1] % 10 - last) < 2) break;last = n / b[i - 1] % 10 , di = 0;}return ans; } int main() {init();ll n , m;scanf("%lld%lld" , &n , &m);printf("%lld\n" , calc(m + 1) - calc(n));return 0; }

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7811439.html

總結

以上是生活随笔為你收集整理的【bzoj1026】[SCOI2009]windy数 数位dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。