首先考慮一下給一個數(shù)如何求它需要多少次操作。

　　顯然用一個單調(diào)棧就可以完成：塞入棧中，將比它大的所有數(shù)都彈出，如果棧中沒有當(dāng)前數(shù)，答案+1。

　　因?yàn)閿?shù)的范圍只有0~9，所以我們可以用一個二進(jìn)制數(shù)來模擬這個棧，并塞到DP的狀態(tài)里。

　　設(shè)$dp[i][j][k]$表示前i位數(shù)，已經(jīng)進(jìn)行了j次操作，棧的狀態(tài)為k的方案數(shù)。

　　每次枚舉一個數(shù)的時候，先把比這個數(shù)大的數(shù)在狀態(tài)中都清零，再看看狀態(tài)中有沒有這個數(shù)，沒有的話答案+1。

　　注意需要把狀態(tài)初始值設(shè)為0在棧中...T T

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #define ll long long using namespace std; ll l, r, K; ll dp[20][20][1<<10]; int a[20]; ll dfs(int pos, int k, int st, bool limit) {if(!pos) return k==K;if(!limit && dp[pos][k][st]!=-1) return dp[pos][k][st];int up=limit?a[pos]:9; ll ans=0;for(int i=0;i<=up;i++){int now=st;for(int j=i+1;j<=9;j++) now^=((now & (1<<j))!=0)<<j;if(st&(1<<i)) ans+=dfs(pos-1, k, now, limit && i==up);else if(k<K) ans+=dfs(pos-1, k+1, now|(1<<i), limit && i==up);}if(!limit) dp[pos][k][st]=ans;return ans; } ll solve(ll x) {int pos=0;while(x) a[++pos]=x%10, x/=10;return dfs(pos, 0, 1, 1); } int main() {memset(dp, -1, sizeof(dp));scanf("%lld%lld%lld", &l, &r, &K);printf("%lld\n", solve(r)-solve(l-1)); } View Code

?

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

總結(jié)

以上是生活随笔為你收集整理的51nod 1623 完美消除（数位DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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