數(shù)位dp,主要用來(lái)解決統(tǒng)計(jì)滿足某類特殊關(guān)系或有某些特點(diǎn)的區(qū)間內(nèi)的數(shù)的個(gè)數(shù)，它是按位來(lái)進(jìn)行計(jì)數(shù)統(tǒng)計(jì)的，可以保存子狀態(tài)，速度較快。數(shù)位dp做多了后，套路基本上都差不多，關(guān)鍵把要保存的狀態(tài)給抽象出來(lái)，保存下來(lái)。

簡(jiǎn)介：

顧名思義，所謂的數(shù)位DP就是按照數(shù)字的個(gè)，十，百，千……位數(shù)進(jìn)行的DP。
數(shù)位DP的題目有著非常明顯的性質(zhì)：

????? 詢問(wèn)[l,r]的區(qū)間內(nèi)，有多少的數(shù)字滿足某個(gè)性質(zhì)

做法根據(jù)前綴和的思想，求出[0,l-1]和[0,r]中滿足性質(zhì)的數(shù)的個(gè)數(shù)，然后相減即可。

算法核心：

關(guān)于數(shù)位DP，貌似寫法還是比較多的，有遞歸的，也有非遞歸的。
下面學(xué)習(xí)一下較好理解，可拓展性較高的遞歸寫法。

LL dfs(int x,int pre,int bo,int limit);

一般需要以上參數(shù)（當(dāng)然具體情況具體分析）。

• x表示當(dāng)前的數(shù)位（一般都是從高位到低位）
• pre表示前一位的數(shù)字
• bo可以表示一些附加條件：是否有前項(xiàng)0，是否包含49，是否當(dāng)前已經(jīng)符合條件……
• limit這個(gè)很重要！它表示當(dāng)前數(shù)位是否受到上一位的限制，比較抽象，舉例說(shuō)明
  如果上限是135，前兩位已經(jīng)是1和3了，現(xiàn)在到了個(gè)位，個(gè)位只能是5以下的數(shù)字

注：如果當(dāng)前受限，不能夠記憶化，也不能返回記憶化的結(jié)果
為了避免多次調(diào)用時(shí) 每次上限不同 而導(dǎo)致的錯(cuò)亂影響

例題：HDU 3555

題意：a到b中有多少個(gè)數(shù)字包含49

思路：

dfs(x,pre,bo,limit)
表示當(dāng)前位置，前一位的數(shù)字，當(dāng)前是否已經(jīng)包含49，以及是否有上界
當(dāng)然，直接搜索肯定TLE，f[x][pre][bo]記憶化即可。

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N = 20; #define LL long long int dig[N]; LL f[N][10][2]; // 數(shù)位，前一位數(shù)，是否符合條件，是否符合限制 [從高位到低位處理] LL dfs(int x, int pre, int bo, int limit){if (x < 0) return bo; // 已經(jīng)枚舉了最后一位if (!limit && f[x][pre][bo] != -1) return f[x][pre][bo]; // 記憶化dpint last = limit ? dig[x] : 9; // 確定這一位的上限是多少LL re = 0;for (int i = 0; i <= last; i++)re += dfs(x - 1, i, bo || (pre == 4 && i == 9), limit && (i == last));if (!limit) f[x][pre][bo] = re; // 當(dāng)前受限，不能夠記憶化，也不能返回記憶化的結(jié)果return re; } LL solve(LL n){int len = 0;while (n){dig[len++] = n % 10;n /= 10;}return dfs(len - 1, 0, 0, 1); } int main(){memset(f, -1, sizeof(f));int T; scanf("%d", &T);while (T--){LL n;cin >> n;cout << solve(n) << endl;}return 0; }

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

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的HDU 3555 Bomb (数位DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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