关于数位动规（入门到进阶，难度中档）
數(shù)位動(dòng)規(guī)，就是對(duì)于數(shù)位進(jìn)行動(dòng)規(guī)（日常一句廢話···）
剛好今天聽(tīng)數(shù)位dp，就總結(jié)一下最近寫(xiě)的題吧。郭神說(shuō)要學(xué)懂?dāng)?shù)位dp，還是要搞懂它內(nèi)部是怎么工作的。比如一個(gè)有大小的數(shù)，我們?cè)谶@里剝奪它作為一個(gè)整數(shù)的所有標(biāo)簽，它現(xiàn)在只不過(guò)是幾個(gè)位置，我們要在上面按照一定的限制放置數(shù)字，除了我給的限制之外，他們位與位之間沒(méi)有任何影響。
比如15651,38983，對(duì)于我的限制來(lái)說(shuō)，這兩個(gè)數(shù)并沒(méi)有什么本質(zhì)區(qū)別，他們都是有五個(gè)位置的，不含前導(dǎo)零，并且完全回文的數(shù)字串，除此之外，什么也不是。
所以，我們就要想辦法把某些限制的數(shù)篩出來(lái)，這就是數(shù)位dp。對(duì)于數(shù)位dp，我見(jiàn)過(guò)循環(huán)遞推的寫(xiě)法，當(dāng)然在我這邊更流行的是記憶化搜索，今天講的重點(diǎn)也是記憶化搜索；通過(guò)我對(duì)數(shù)位dp的理解，我整理了一個(gè)類似于記憶化搜索模板的東西，請(qǐng)大家先從下面看一兩道題之后再來(lái)看這個(gè)模板：
這個(gè)dfs函數(shù)包含幾個(gè)參數(shù)，比如說(shuō)當(dāng)前決策的位（len）、題目中給的限制條件所需要的一兩個(gè)參數(shù)、當(dāng)前是否在數(shù)值范圍的上界、有時(shí)還有前導(dǎo)零問(wèn)題。具體題目還需具體分析。請(qǐng)看下圖：
這只是一個(gè)比較籠統(tǒng)的模板，具體題目更要靈活應(yīng)用！
下面分享幾道水題：
一、HDU 3555 Bomb
這個(gè)題一句話就是說(shuō)求1~n中含49的數(shù)字有多少，那我們直接在狀態(tài)中記錄決策時(shí)的最后兩位，出現(xiàn)四十九的最后返回1，否則0；大家看這道題，前導(dǎo)零不前導(dǎo)零就沒(méi)什么影響，因?yàn)?9又不可能出現(xiàn)在前導(dǎo)零中，所以既不會(huì)出現(xiàn)多余的答案，也不會(huì)漏掉正確的答案！
請(qǐng)看代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=21;char ch; 8 long long f[MAXN][10][2],n,m,k,dig[MAXN],len1; 9 long long dfs(int len,int la1,int la2,bool flag,bool ap){ 10 if(len>len1) return (int)ap; 11 if(!flag&&~f[len][la2][(int)ap]) return f[len][la2][(int)ap]; 12 long long tot=0;int end=flag?dig[len]:9; 13 for(int i=0;i<=end;i++) 14 tot+=dfs(len+1,la2,i,flag&&(i==end),((la2==4)&&(i==9))||ap); 15 if(!flag) f[len][la2][(int)ap]=tot;return tot; 16 } 17 int main(){ 18 scanf("%lld",&k); 19 while(k--){ 20 len1=0;ch=getchar();long long ans=0; 21 while(!isdigit(ch)) ch=getchar(); 22 while(isdigit(ch)) dig[++len1]=ch-'0',ch=getchar(); 23 memset(f,-1,sizeof(f));ans=dfs(1,0,0,1,0); 24 printf("%lld\n",ans); 25 } 26 } 數(shù)位dp代碼很短，也好寫(xiě)，尤其是，還很模板，作為入門(mén)題在適合不過(guò)啦！
?
二、HDU 2089 不要62
這個(gè)題乍一看根上一題一模一樣！仔細(xì)一看也是一模一樣，狀態(tài)里還是記兩位，只不過(guò)在判62的基礎(chǔ)上判一下有沒(méi)有4就好了！
請(qǐng)看代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<string> 8 #include<queue> 9 using namespace std; 10 long long f[10][10],d[10]; 11 long long n,m,k,l,r; 12 void take() 13 { 14 f[0][0]=1; 15 for(int i=1;i<=7;i++) 16 for(int j=0;j<=9;j++) 17 for(int k=0;k<=9;k++) 18 if(j!=4&&!(j==6&&k==2)) 19 f[i][j]+=f[i-1][k]; 20 return ; 21 } 22 int solve(int n) 23 { 24 int ans=0,len=0; 25 while(n){ 26 d[++len]=n%10; 27 n /= 10; 28 } 29 d[len+1]=0; 30 for(int i=len;i>=1;--i){ 31 for(int j=0;j<d[i];j++){ 32 if(d[i+1]!=6||j!=2) 33 ans+=f[i][j]; 34 } 35 if(d[i]==4||(d[i+1]==6&&d[i]==2)) break; 36 } 37 return ans; 38 } 39 int main() 40 { 41 take(); 42 while(~scanf("%d%d",&m,&n)&&m&&n){ 43 printf("%d\n", solve(n+1)-solve(m)); 44 } 45 return 0; 46 } 數(shù)位dp這道題根上一道題我用的方法不同，這是用循環(huán)做的，有興趣的同學(xué)可以試著用模板虐一下這題，也可以學(xué)學(xué)循環(huán)寫(xiě)法拓寬思路。
?
三、HDU 3709 Balance Number
這個(gè)題也很模板，平衡的數(shù)嘛，我們就枚舉作為支點(diǎn)的那個(gè)數(shù)，然后一個(gè)參數(shù)記錄題目限制，直接套用模板。但是這個(gè)題對(duì)于0來(lái)說(shuō)就用一點(diǎn)影響了，000000這種數(shù)，每一位都是支點(diǎn)，都會(huì)被計(jì)算一次，最后要從答案中把多計(jì)算的減去！
請(qǐng)看代碼：
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define ll long long 7 using namespace std; 8 const int MAXN=20; 9 ll f[MAXN][MAXN][MAXN*100],l,r;int t,dig[MAXN]; 10 ll dfs(int pos,int x,int s,bool flag){ 11 if(pos<=0) return !s;if(s<0) return 0; 12 if(!flag&&~f[pos][x][s]) return f[pos][x][s]; 13 int end=flag?dig[pos]:9;ll ans=0; 14 for(int i=0;i<=end;i++) 15 ans+=dfs(pos-1,x,s+i*(pos-x),flag&&(i==end)); 16 if(!flag) f[pos][x][s]=ans;return ans; 17 } 18 ll solve(ll x){ 19 if(x<0) return 0;int len=0;ll ans=0; 20 while(x) dig[++len]=x%10,x/=10; 21 for(int i=1;i<=len;i++) ans+=dfs(len,i,0,1); 22 return ans-len+1; 23 } 24 int main(){ 25 memset(f,-1,sizeof(f)); 26 scanf("%d",&t);while(t--){ 27 scanf("%lld%lld",&l,&r); 28 printf("%lld\n",solve(r)-solve(l-1)); 29 }return 0; 30 } 數(shù)位dp也特別短，幾乎就是模板！
?
四、luoguP3413 萌數(shù)
這個(gè)題需要稍微稍微動(dòng)下腦筋，也特別簡(jiǎn)單，含長(zhǎng)度至少為2的回文部分，我們可以簡(jiǎn)單地想成兩種情況！分別是奇回文和偶回文，我們想，一個(gè)奇回文一定含有一個(gè)長(zhǎng)度為3的回文部分（我稱之為回文核），一個(gè)偶回文一定含有一個(gè)長(zhǎng)度為2的回文核，那么這個(gè)題就解決了，只需要記錄當(dāng)前決策前兩個(gè)數(shù)的狀態(tài)，分情況判斷。但是這個(gè)題有一個(gè)問(wèn)題，前導(dǎo)零個(gè)數(shù)超過(guò)2的都會(huì)被記錄，需要處理前導(dǎo)零的問(wèn)題。
請(qǐng)看代碼：
1 #include<cstdio> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 struct data{ 7 long long a,b;//a表示所有情況，b表示已有回文 8 }d[1005][11][11]; 9 char s1[1005],s2[1005]; 10 int nl,nr,len,i,dp[1005][11][11],digit[8000],mod=1000000007;//dp數(shù)組表示是否記錄過(guò)，digit表示數(shù)位數(shù)字 11 inline data dfs(int len,int state,int ss,bool flag,bool ff){//len表示當(dāng)前位置，state，ss分別表示兩位數(shù)字，flag表示是否要枚舉到9，ff表示當(dāng)前是否是這個(gè)數(shù)的第一個(gè)數(shù)字，即我說(shuō)的那個(gè)注意點(diǎn) 12 if(len==0){ 13 data zs; zs.a=1; zs.b=0; 14 return zs;}//邊界 15 if(dp[len][state][ss]&&flag==false&&ff==false)return d[len][state][ss]; data z; z.a=z.b=0;//如果已經(jīng)訪問(wèn)過(guò)直接返回 16 int meiju=flag?digit[len]:9; //確定枚舉范圍 17 for(int i=0;i<=meiju;i++){ 18 data zs=dfs(len-1,ff&i==0?10:i,ff&&i==0?10:state,flag&&(i==digit[len]),ff&&(i==0)); 19 z.a+=zs.a; z.b+=zs.b; if(state==i||ss==i)z.b+=zs.a-zs.b; z.a%=mod; z.b%=mod;//是否產(chǎn)生回文 20 } 21 if(flag==false&&ff==false){dp[len][state][ss]=true;d[len][state][ss]=z;} //存儲(chǔ) 22 return z; 23 } 24 int main(){ 25 memset(dp,0,sizeof(dp)); 26 scanf("%s%s",&s1,&s2); 27 nl=strlen(s1); nr=strlen(s2);len=nl; 28 for(i=0;i<nl;i++)digit[len-i]=s1[i]-'0'; int flag=false; 29 for(i=0;digit[i]==0;i++); digit[i]--; if(i==1&&digit[i]==1)nl--; for(i--;i;i--)digit[i]=9;//將l減1 30 long long zs=dfs(len,10,10,true,true).b; 31 len=nr; 32 for(int i=0;i<nr;i++)digit[len-i]=s2[i]-'0'; 33 cout<<(dfs(len,10,10,true,true).b-zs+mod)%mod<<endl; 34 } 數(shù)位dp我記得好像寫(xiě)過(guò)這題題解。額不對(duì)，我寫(xiě)的是Round Number!
?
?
五、當(dāng)然是Round Number咯
?甭解釋了，寫(xiě)的非常清楚了！！
?
六、luogu 2657 Windy數(shù)
這個(gè)提也比較模板，可以說(shuō)是只記錄兩個(gè)數(shù)就好，但我用的貌似是循環(huán)做法，可以看一下。
請(qǐng)看代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cstring> 6 #include<string> 7 #include<algorithm> 8 #include<queue> 9 using namespace std; 10 int f[15][15],n,m,l,k,r; 11 int a[15]; 12 void init() 13 { 14 for(int i=0;i<=9;i++) f[1][i]=1; 15 for(int i=2;i<=10;i++){ 16 for(int j=0;j<=9;j++){ 17 for(int k=0;k<=9;k++){ 18 if(abs(j-k)>=2) f[i][j]+=f[i-1][k]; 19 } 20 } 21 } 22 } 23 int solve(int x) 24 { 25 memset(a,0,sizeof(a)); 26 int len=0,ans=0; 27 while(x){ 28 a[++len]=x%10; 29 x/=10; 30 } 31 for(int i=1;i<=len-1;i++){ 32 for(int j=1;j<=9;j++){ 33 ans+=f[i][j]; 34 } 35 } 36 for(int i=1;i<a[len];i++){ 37 ans+=f[len][i]; 38 } 39 for(int i=len-1;i;i--){ 40 for(int j=0;j<=a[i]-1;j++){ 41 if(abs(j-a[i+1])>=2) ans+=f[i][j]; 42 } 43 if(abs(a[i+1]-a[i])<2) break; 44 } 45 return ans; 46 } 47 int main() 48 { 49 init(); 50 scanf("%d%d",&n,&m); 51 cout<<solve(m+1)-solve(n)<<endl; 52 return 0; 53 } 數(shù)位dp處理邊界的那一段長(zhǎng)一些。
?
七、luogu 2602 數(shù)字計(jì)數(shù)
這個(gè)題就不是純模板了，放在這里，權(quán)當(dāng)開(kāi)發(fā)智力！這個(gè)題需要試幾組比較整的數(shù)來(lái)找找規(guī)律，同時(shí)還要注意比如0,1之類的細(xì)節(jié)，思慮周全再寫(xiě)會(huì)更好！
請(qǐng)看代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cstring> 7 #include<string> 8 #include<queue> 9 using namespace std; 10 long long a,b; 11 long long ten[20],f[20],cnta[20],cntb[20]; 12 void solve(long long x,long long *cnt) 13 { 14 long long num[20]; 15 int len=0; 16 while(x){ 17 num[++len]=x%10; 18 x/=10; 19 } 20 for(int i=len;i;i--){ 21 for(int j=0;j<=9;j++){ 22 cnt[j]+=f[i-1]*num[i]; 23 } 24 for(int j=0;j<num[i];j++){ 25 cnt[j]+=ten[i-1]; 26 } 27 long long num2=0; 28 for(int j=i-1;j>=1;j--){ 29 num2=num2*10+num[j]; 30 } 31 cnt[num[i]]+=num2+1; 32 cnt[0]-=ten[i-1];//處理前導(dǎo)零問(wèn)題； 33 } 34 } 35 int main() 36 { 37 scanf("%lld%lld",&a,&b); 38 ten[0]=1;//輔助數(shù)組，代表10的i次方 39 for(int i=1;i<=15;i++){ 40 f[i]=f[i-1]*10+ten[i-1]; 41 ten[i]=ten[i-1]*10; 42 } 43 solve(a-1,cnta); 44 solve(b,cntb); 45 for(int i=0;i<=9;i++) { 46 cout<<cntb[i]-cnta[i]<<" "; 47 } 48 puts(""); 49 return 0; 50 } 數(shù)位dp?
八、如果說(shuō)前面都是水題，那這一道算是不那么水的題。luogu 3286 方伯伯的商場(chǎng)之旅
我們考慮代價(jià)是怎樣計(jì)算的，從Balanced Number那里，我們可以得到一些啟發(fā)，大概也是要找某個(gè)算起來(lái)比較平衡的數(shù)位來(lái)貢獻(xiàn)代價(jià)！我們仔細(xì)觀察，假如我們要把支點(diǎn)從當(dāng)前位向右移動(dòng)一位，代價(jià)會(huì)怎樣變化？于是乎我們想到了用前綴和來(lái)計(jì)算支點(diǎn)的偏移，這樣，我們通過(guò)兩個(gè)dfs函數(shù)，首先，假定所有數(shù)的支點(diǎn)都在第一位（最左邊一位），然后一位一位向右偏移，如果當(dāng)前偏移能減小代價(jià)，那么就用答案減去這個(gè)值，否則就答案減去0；一直推到最后一位，這個(gè)答案就確定了！附一詳細(xì)題解：errrrrrrrr
請(qǐng)看代碼：
1 //%%%%%%%尹兄 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define ms(a,x) memset(a,x,sizeof(a)) 8 #define ll long long 9 using namespace std; 10 const int MAXN=60; 11 ll f[MAXN][MAXN*50],l,r; 12 int k,n=0,dig[MAXN]; 13 ll dfs1(int len,int s,bool flag){ 14 if(len<=0) return s; 15 if(!flag&&~f[len][s]) return f[len][s]; 16 int end=flag?dig[len]:k-1;ll ans=0; 17 for(int i=0;i<=end;i++) 18 ans+=dfs1(len-1,s+i*(len-1),flag&&i==end); 19 if(!flag) f[len][s]=ans;return ans; 20 } 21 ll dfs2(int len,int s,int m,bool flag){ 22 if(s<0) return 0;if(len<=0) return s; 23 if(!flag&&~f[len][s]) return f[len][s]; 24 int end=flag?dig[len]:k-1;ll ans=0; 25 for(int i=0;i<=end;i++) 26 ans+=dfs2(len-1,s+(len>=m?i:-i),m,flag&&i==end); 27 if(!flag) f[len][s]=ans;return ans; 28 } 29 ll solve(ll x){ 30 n=0;while(x) dig[++n]=x%k,x/=k; 31 ms(f,-1);ll ans=dfs1(n,0,1); 32 for(int i=2;i<=n;i++) 33 ms(f,-1),ans-=dfs2(n,0,i,1); 34 return ans; 35 } 36 int main(){ 37 scanf("%lld%lld%d",&l,&r,&k); 38 printf("%lld\n",solve(r)-solve(l-1)); 39 return 0; 40 } 數(shù)位dp可以看到，兩個(gè)函數(shù)都是由模板改過(guò)來(lái)的，所以這題也沒(méi)有那么難
?
通過(guò)上述這些題目我們可以看到，大部分的數(shù)位dp，都是通過(guò)模板進(jìn)行一個(gè)變形，萬(wàn)變不離其宗，有的時(shí)候一些玄學(xué)優(yōu)化會(huì)加大他的難度，所以數(shù)位dp說(shuō)難也難，說(shuō)不難也不難請(qǐng)各位勇敢的直面它。
轉(zhuǎn)載于:https://www.cnblogs.com/Alan-Luo/articles/9514428.html
總結(jié)
以上是生活随笔為你收集整理的关于数位动规（入门到进阶，难度中档）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 将dos格式文件转换为unix格式
- 下一篇： 【Codeforces】CF 5 C L