題意

區(qū)間[A,B]上，總共有多少個不含前導(dǎo)零且相鄰兩個數(shù)字之差至少為2的正整數(shù)？

思路

狀態(tài)設(shè)計非常簡單，只需要pos、limit和一個前驅(qū)數(shù)pre就可以了，每次枚舉當(dāng)前位時判斷是否與上一位相差2即可。一個需要注意的地方是第一位不用比較，所以我們還需要一個flag標(biāo)志記錄當(dāng)前pos位是不是第一位。

代碼

? [cpp] #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, m) for (int i = begin; i < begin+m; i ++) using namespace std; typedef long long LL; typedef vector <int> VI; typedef set <int> SETI; typedef queue <int> QI; typedef stack <int> SI; const int oo = 0x7fffffff; int dp[12][10][2]; VI num; int dfs(int pos, int pre, bool flag, int limit){ if (pos == -1) return 1; if (!limit && ~dp[pos][pre][flag]) return dp[pos][pre][flag]; int end = limit?num[pos]:9, res = 0; for (int i = 0; i <= end; i ++){ if (flag || abs(i - pre) >= 2){ res += dfs(pos-1, i, flag&&(i == 0),limit&&(i==end)); } } return limit?res:dp[pos][pre][flag] = res; } int cal(int x){ num.clear(); while(x){ num.push_back(x%10); x /= 10; } return dfs(num.size()-1, 0, 1, 1); } int main(){ int a,b; MEM(dp, -1); while(scanf("%d %d", &a, &b) != EOF){ printf("%d\n", cal(b)-cal(a-1)); } return 0; } [/cpp]

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/p/4114315.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1026 windy数 (数位DP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。