打了幾個(gè)數(shù)位$dp$，發(fā)現(xiàn)自己除了會(huì)打模板之外沒(méi)有任何長(zhǎng)進(jìn)，遇到非模板題依然什么都不會(huì)

那么接下來(lái)這篇文章將介紹如何打模板（滑稽）

假設(shè)我們要處理$l----r$

采用記憶化搜索的方式，枚舉$<=r$每一種情況，枚舉每一位，然后再枚舉$<=l-1$每一種情況，然后兩個(gè)值相減即可

我們可以比較輕松打出一個(gè)模板

ll dfs(ll x,ll pre,ll lead,ll limit){if(x>pos) return 1;if(!limit&&f[x][pre]) return f[x][pre];ll ans=0;ll mx=limit?maxn[pos-x+1]:9;for(ll i=0;i<=mx;i++){if(????????) continue;if(lead&&i==0) ans+=dfs(x+1,-2,1,limit&&(i==mx));else ans+=dfs(x+1,i,0,limit&&(i==mx));}if(!limit&&!lead) f[x][pre]=ans;return ans; }

解釋一下$limit$是什么

假設(shè)有一個(gè)數(shù)

$1\?? 2\? 3\? 4\? 5\? 6$

$1\?? 2\? 3\? ?\? ?\? ?$

我們枚舉到第四位時(shí)最多枚舉到$4$，

$1\?? 2\? 3\? 4\? 5\? 6$

$1\?? 2\? 2\? ?\? ?\? ?$

這時(shí)我們枚舉到第四位最多枚舉到$9$

$limit$就是判斷這個(gè)的

那么為什么要在$！limit$下才記憶化呢？

如果在所有情況下我們都記錄f，那么假如之前枚舉到$9$時(shí)你記錄了一個(gè)答案，然后當(dāng)前位有$limit$限制根本枚舉不到$9$，你仍然用了這個(gè)f會(huì)出現(xiàn)錯(cuò)誤

當(dāng)然你這樣記憶化也可以這樣避免沖突

ll dfs(ll x,ll limit,ll tmp,ll d){if(f[x][limit][tmp][d]) return f[x][limit][tmp][d];……………… f[x][limit][tmp][d]=ans;return ans; }

解釋一下$lead$

處理前導(dǎo)0用的，

有的時(shí)候

$0\?? 0\? 0\? 4\? 5\? 6$

也被認(rèn)為是合法的，這時(shí)處理可能會(huì)出現(xiàn)問(wèn)題，$lead$特判特殊處理

那么我們看幾道模板題

例題

windy數(shù)

Windy 定義了一種 Windy 數(shù)：不含前導(dǎo)零且相鄰兩個(gè)數(shù)字之差至少為2的正整數(shù)被稱為 Windy 數(shù)。

Windy 想知道，在l和r 之間，包括l 和 r ，總共有多少個(gè) Windy 數(shù)？

非常簡(jiǎn)單對(duì)不對(duì)

套模板

代碼：

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 50 ll f[A][A],maxn[A]; ll pos=0,a,b; ll dfs(ll x,ll pre,ll lead,ll limit){if(x>pos) return 1;if(!limit&&f[x][pre]) return f[x][pre];ll ans=0;ll mx=limit?maxn[pos-x+1]:9; // printf("mx=%lld\n",mx);for(ll i=0;i<=mx;i++){if(abs(pre-i)<2) continue;if(lead&&i==0) ans+=dfs(x+1,-2,1,limit&&(i==mx));else ans+=dfs(x+1,i,0,limit&&(i==mx)); // printf("ans=%lld\n",ans); }if(!limit&&!lead) f[x][pre]=ans;return ans; } ll solve(ll x){pos=0;memset(f,0,sizeof(f));while(x){maxn[++pos]=x%10;x/=10;}ll ans=dfs(1,-2,1,1);return ans; } int main(){scanf("%lld%lld",&a,&b);swap(a,b);printf("%lld\n",solve(a)-solve(b-1)); }

不要62

$l---r$間數(shù)位上不含$4$且沒(méi)有$62$相連的數(shù)個(gè)數(shù)

套模板

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 50 ll f[A][A],maxn[A]; ll pos=0,a,b; ll dfs(ll x,ll pre,ll limit){if(!x) return 1;if(!limit&&f[x][pre]) return f[x][pre]; // printf("x=%lld pre=%lld limit=%lld\n",x,pre,limit);ll ans=0;ll mx=limit?maxn[x]:9;for(ll i=0;i<=mx;i++){if(pre==6&&i==2) continue;if(i==4) continue;ans+=dfs(x-1,i,limit&&(i==mx));} // printf("ans=%lld\n",ans);if(!limit) f[x][pre]=ans;return ans; } ll solve(ll x){pos=0;memset(f,0,sizeof(f));while(x){maxn[++pos]=x%10;x/=10;}ll ans=dfs(pos,0,1);return ans; } int main(){a=233,b=233;while(a!=0&&b!=0){scanf("%lld%lld",&a,&b);if(a<b)swap(a,b);if(a==0||b==0){return 0;}printf("%lld\n",solve(a)-solve(b-1));} }

手機(jī)號(hào)碼

至少$3$個(gè)相鄰的相同的數(shù)，$8$ $4$不能同時(shí)出現(xiàn)

套模板，注意下特判，不然會(huì)70到自閉

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 30 ll f[A][A][A][2][2][2],pos[A]; ll tot=0,a,b; ll dfs(ll x,ll prer,ll pre,ll limit,ll _4,ll _8,ll ok){if(_4&&_8) return 0;if(x>tot&&!ok) return 0;if(x>tot&&ok) return 1;if(!limit&&f[x][prer][pre][_4][_8][ok]) return f[x][prer][pre][_4][_8][ok];ll maxn=limit?pos[tot-x+1]:9;ll ans=0;for(ll i=0;i<=maxn;i++){if(x==1&&i==0) continue;if(_4&&i==8) continue;if(_8&&i==4) continue;if(pre==prer&&i==pre&&i==prer)ans+=dfs(x+1,pre,i,(limit&&i==maxn),(_4||i==4),(_8||i==8),1);else ans+=dfs(x+1,pre,i,limit&&(i==maxn),(_4||i==4),(_8||i==8),ok); // printf("ans=%lld i=%lld maxn=%lld\n",ans,i,maxn); }if(!limit)f[x][prer][pre][_4][_8][ok]=ans;return ans; } ll solve(ll x){tot=0;if(x<1e10) return 0;memset(f,0,sizeof(f));while(x){pos[++tot]=x%10;x/=10;}ll ans=dfs(1,0,0,1,0,0,0);return ans; } int main(){scanf("%lld%lld",&a,&b);if(a<b) swap(a,b);printf("%lld\n",solve(a)-solve(b-1)); }

花神的數(shù)論題

設(shè) sum(i) 表示 i 的二進(jìn)制表示中 1 的個(gè)數(shù)。給出一個(gè)正整數(shù) N ，花神要問(wèn)你派(Sum(i)),也就是 sum(1)—sum(N) 的乘積。

套模板，等等，我要套什么，

這個(gè)題不算很板，值得思考思考。

數(shù)位dp計(jì)算出所有二進(jìn)制下sum個(gè)數(shù)，然后快速冪處理一下，

代碼

#include<bits/stdc++.h> using namespace std; #define A 53 #define mod 10000007 #define ll long long ll n,tot=0,sum=0; ll f[A][2][A][A],ans[A],pos[A]; ll dfs(ll cur,ll up,ll tmp,ll d){if(!cur)return tmp==d;if(~f[cur][up][tmp][d])return f[cur][up][tmp][d];ll lim=up?pos[cur]:1;ll ret=0;for(ll i=0;i<=lim;i++)ret+=dfs(cur-1,up&&i==lim,tmp+(i==1),d);return f[cur][up][tmp][d]=ret; } ll meng(ll a,ll b){ll ret=1;while(b)ret=ret*(b&1?a:1)%mod,a=a*a%mod,b>>=1;return ret; } ll solve(ll x){sum=1;while(x){pos[++tot]=x&1;x>>=1;}for(ll i=1;i<=tot;i++){memset(f,-1,sizeof(f));ans[i]=dfs(tot,1,0,i);}for(ll i=1;i<=tot;i++){sum=(sum*max(meng(i,ans[i]),1ll))%mod;}return sum; } int main(){scanf("%lld",&n);printf("%lld\n",solve(n)); }

剩下一些題都不算很板

數(shù)數(shù)

淘金

方伯伯商場(chǎng)之旅

?

題解慢慢補(bǔ)充八

?

那么你現(xiàn)在會(huì)模板了嗎？

轉(zhuǎn)載于:https://www.cnblogs.com/znsbc-13/p/11328399.html

總結(jié)

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

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