數(shù)位動態(tài)規(guī)劃?
????數(shù)位動態(tài)規(guī)劃是求解一個大區(qū)間[L, R]中間滿足條件Q的所有數(shù)字的個數(shù)（或者和，或其他）的一種方法。它通過分析每一位上的數(shù)字，一般用 dp[len][digit][...] 來表示狀態(tài)“l(fā)en位長的數(shù)字，最高位數(shù)字為digit所具有的xx特性”，利用記憶化搜索保存中間結(jié)果，從而加快求解速度。?
????通過求 f(n) 從0到n中滿足條件Q的數(shù)字的個數(shù)，則所求的結(jié)果為 f(R) - f(L-1).?
????大多數(shù)數(shù)位dp都可以用一個DFS函數(shù)來進(jìn)行記憶化搜索：

//len數(shù)字的位數(shù)，digit最高位的值，end_flag 表示digit是否是第len位（從低位向高位數(shù)，個位為第1位） 的范圍邊界 int Dfs(int len, int digit, bool end_flag){//超出邊界if (len <= 0 || digit > 9 || digit < 0)return 0;//記憶化搜索，如果之前已經(jīng)求出來了，則返回。注意這里要求 end_flag為falseif (!end_flag && dp[len][digit] != -1)return dp[len][digit];// 最簡單情況看數(shù)字是否滿足要求if (len == 1)return dp[len][digit] = xxx;//如果當(dāng)前位是邊界數(shù)字N對應(yīng)位的最大值，則下一位的范圍只能從0到邊界數(shù)字N的下一位的最大值。否則為0 到 9int end = end_flag ? bits[len - 2] : 9; int ans = 0;for (int i = 0; i <= end; i++){ans += Dfs(len - 1, i, end_flag && (i==end));}if (!end_flag) //digit不是第len位的最高范圍，則可以將結(jié)果緩存dp[len][digit] = ans;return ans; }

?

題目大意?
????給定一個區(qū)間[L, R]，求區(qū)間內(nèi)滿足條件“數(shù)位上不含有4，且不含有62（62必須連續(xù)）”的數(shù)字的個數(shù)。

分析?
????直接套用模板

實(shí)現(xiàn)

#include<iostream> #include<stdio.h> using namespace std; int dp[9][10]; int bits[8];//用dfs進(jìn)行記憶化搜索， dp[len][digit] 表示 len位數(shù)字，最高位為digit滿足條件的個數(shù). 這里對數(shù)字范圍沒有限制！ //搜索的時候，若要進(jìn)行記憶化，需要 dp[len][digit]的結(jié)果對數(shù)字范圍沒有限制，因此需要判斷 end_flag來決定是否進(jìn)行記憶。//len數(shù)字的位數(shù)，digit最高位的值，end_flag 表示digit是否是第len位（從低位向高位數(shù)，個位為第1位） 的范圍邊界 int Dfs(int len, int digit, bool end_flag){//超出邊界if (len <= 0 || digit > 9 || digit < 0)return 0;//記憶化搜索，如果之前已經(jīng)求出來了，則返回。注意這里要求 end_flag為falseif (!end_flag && dp[len][digit] != -1)return dp[len][digit];// 最簡單情況看數(shù)字是否滿足要求if (len == 1)return dp[len][digit] = (digit != 4);if (digit == 4)return dp[len][digit] = 0;//如果當(dāng)前位是邊界數(shù)字N對應(yīng)位的最大值，則下一位的范圍只能從0到邊界數(shù)字N的下一位的最大值。否則為0 到 9int end = end_flag ? bits[len - 2] : 9; int ans = 0;for (int i = 0; i <= end; i++){if (!(digit == 6 && i == 2)) //除去 62連續(xù)的情況ans += Dfs(len - 1, i, end_flag && (i==end));}if (!end_flag) //digit不是第len位的最高范圍，則可以將結(jié)果緩存dp[len][digit] = ans;return ans; }//將數(shù)字n的各個位上的范圍求出來，保存到bits數(shù)組中，返回?cái)?shù)字n的長度 int Init(int n){ memset(bits, 0, sizeof(bits));int k = 0;while (n){bits[k++] = n % 10;n /= 10;}return k; }int Solve(int n){ int len = Init(n); //數(shù)字長度為len，則為了避免首位遍歷從0到bits[len-1]，給數(shù)字增加一個前導(dǎo)0。//len + 1位，首位為0，且0是最高位的邊界int ans = Dfs(len + 1, 0, true);return ans; } int main(){int m, n;memset(dp, -1, sizeof(dp));while (scanf("%d %d", &m, &n)){if (m == 0 && n == 0)break; int ret1 = Solve(m-1);int ret2 = Solve(n);int ret = ret2 - ret1;printf("%d\n", ret);}return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的hdu_2089 不要62的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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