?

// pos = 當(dāng)前處理的位置(一般從高位到低位) // pre = 上一個位的數(shù)字(更高的那一位) // state = 要達到的狀態(tài),如果為1則可以認為找到了答案,到時候用來返回, // 　　 給計數(shù)器+1。 // limit = 是否受限,也即當(dāng)前處理這位能否隨便取值。如567,當(dāng)前處理6這位, // 　　 如果前面取的是4,則當(dāng)前這位可以取0-9。如果前面取的5,那么當(dāng)前 // 　　 這位就不能隨便取，不然會超出這個數(shù)的范圍,所以如果前面取5的 // 　　 話此時的limit=1,也就是說當(dāng)前只可以取0-6。 // // 用dp數(shù)組保存這三個狀態(tài)是因為往后轉(zhuǎn)移的時候會遇到很多重復(fù)的情況。// 這里以 不要49 為例子講解typedef long long LL; LL dp[pos][pre][state];//這里為了好看直接用每個維度的含義來定義dp //注意：數(shù)位dp至少有一個維度寫pos，也就是每一位的狀態(tài) //其余的狀態(tài)有幾個就需要開幾個維度int b[pos];//儲存每一位的最高位，用來更新limitLL dfs(int pos,int pre,bool state,bool limit) {//已結(jié)搜到盡頭,返回"是否找到了答案"這個狀態(tài)。if(pos == -1)return state;//dp里保存的是完整的,也即不受限的答案,所以如果滿足的話,可以直接返回。if(!limit && dp[pos][pre][state] != -1)return dp[pos][pre][state];int up = limit ? b[pos] : 9;LL ans = 0;//往下搜的狀態(tài)表示的很巧妙,status用||是因為如果前面找到了答案那么后面//還有沒有答案都無所謂了。而limit用&&是因為只有前面受限、當(dāng)前受限才能//推出下一步也受限，比如567,如果是46X的情況,雖然6已經(jīng)到盡頭,但是后面的//個位仍然可以隨便取,因為百位沒受限,所以如果個位要受限,那么前面必須是56。////這里用"不要49"一題來做例子。for(int i = 0;i <= up;i ++)ans += dfs(pos - 1,i,state || (pre == 4 && i == 9),limit && (i == b[pos]));//DP里保存完整的、取到盡頭的數(shù)據(jù)if(!limit)dp[pos][pre][state] = ans;return ans; }LL solve(LL n) {int cnt=0;while(n){b[cnt++]=n%10;n/=10;}return dfs(cnt-1,-1,false,true); }int main() {memset(dp,-1,sizeof(dp));LL a,b;cin>>a>>b;cout<<solve(b)-solve(a-1)<<endl; }

?

總結(jié)

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

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