最近刷題的同時還得填填坑，說來你們也不信，我還不會數位dp。

照例推幾篇博客：
數位DP講解
數位dp 的簡單入門
這兩篇博客講的都很好，不過代碼推薦記搜的形式，不僅易于理解，還短。

數位dp的式子一般是這樣的：dp[i][][]表示到第\(i\)位，而后面幾維就因題而異了。
不過通用的思想就是利用前綴相減求出區間信息。
算了上題吧。

[SCOI2009]windy數
這都說是數位dp入門題。
根據這題，受到影響的數只有相鄰兩個，因此dp[i][j]表示到第\(i\)位（從高往低）上一位的數\(j\)的答案。
接下來的關鍵在于怎么判斷到達上界的情況。那么我們在搜索的時候加一個bool變量_Max表示是否到達上界，如果是，那么這一位的最大值就是該位上的數，否則就是9。
然后關于前導零，我又開了一個bool變量zero判斷他之前有沒有過非0的數。
接下來就是記搜的內容了。先寫一個爆搜，然后把答案存在dp里，基本就是記搜了。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 12; inline ll read() {ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) last = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(last == '-') ans = -ans;return ans; } inline void write(ll x) {if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0'); }int dp[maxn][maxn], num[maxn], cnt = 0;In int dfs(int len, int las, bool _Max, bool zero) {if(!len) return 1; //表示出現了一個符合條件的數,就返回1if(!_Max && !zero && dp[len][las] != -1) return dp[len][las];//只有普通情況才可以返回記搜的答案.int pos, ret = 0, Max = _Max ? num[len] : 9;for(int i = 0; i <= Max; ++i){if(abs(i - las) < 2) continue;pos = (zero && !i) ? -INF : i; //如果前面都是0且這一位還填0，就標記為INFret += dfs(len - 1, pos, _Max && i == Max, pos == -INF);}if(!_Max && !zero) dp[len][las] = ret;return ret; }In int solve(int n) {Mem(dp, -1); cnt = 0;while(n) num[++cnt] = n % 10, n /= 10; //處理每一位return dfs(cnt, -INF, 1, 1); }int main() {int a = read(), b = read();write(solve(b) - solve(a - 1)), enter;return 0; }

luogu P3413 SAC#1 - 萌數
這題反正我是不會，看了題解也沒懂。最后在dukelv的幫助下搞明白了。
首先題解中有很多篇用了正難則反的思想，但其實沒必要。
考慮最小的回文串，無非兩種：aa, aba。
所以我們只用找出這兩種回文串即可。因為大的回文串比如acbbca，在搜bb的時候，下幾個狀態就包括這個回文串了。
那么就要討論奇偶，所以爆搜的時候開兩個變量pre,per分別記錄上一位和上上一位，然后判斷和當前位是否構成回文串。
別忘了還可能會出現構不成萌數的情況，所以dp方程除了dp[i][j]表示到了第\(i\)位，這一位填\(i\)，還應再加一位[0/1]表示當前是否存在萌數，這樣能剪枝不少。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 1e3 + 5; const ll mod = 1e9 + 7; inline ll read() {ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) last = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(last == '-') ans = -ans;return ans; } inline void write(ll x) {if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0'); }char a[maxn], b[maxn]; int num[maxn], len = 0;ll dp[maxn][10][2]; In ll dfs(int pos, int pre, int per, bool _t, bool _k, bool _Max) {if(!pos) return _t; //_t表示當前是否存在萌數if(!_Max && dp[pos][pre][_t] != -1) return dp[pos][pre][_t];int Max = _Max ? num[pos] : 9;ll ret = 0;for(int i = 0; i <= Max; ++i)ret += dfs(pos - 1, i, _k ? pre : -1, _t || (i == pre && _k) || (i == per && _k), _k || i, _Max && i == Max), ret %= mod;if(!_Max && _k && per != -1) dp[pos][pre][_t] = ret % mod;return ret; } In ll solve(char* s) {len = strlen(s + 1);for(int i = 1; i <= len; ++i) num[i] = s[i] - '0';reverse(num + 1, num + len + 1);Mem(dp, -1);return dfs(len, -1, -1, 0, 0, 1); }int main() {scanf("%s%s", a + 1, b + 1);int tp = strlen(a + 1);reverse(a + 1, a + tp + 1);int pos = 1; //別忘了是高精減1……--a[pos];while(pos < tp && a[pos] < '0') a[pos++] = '9', --a[pos];while(tp > 1 && a[tp] <= '0') a[tp--] = '\0';reverse(a + 1, a + tp + 1);write((solve(b) - solve(a) + mod) % mod), enter;return 0; }

轉載于:https://www.cnblogs.com/mrclr/p/10367978.html

總結

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

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