初探数位dp
前言：這是蒟蒻第一次寫算法系列，請諸位大佬原諒文筆與排版。
?
?
一、導(dǎo)入
在刷題的時候，我們有時會見到這樣一類問題：在區(qū)間$[l,r]$內(nèi)，共有多少個整數(shù)滿足某種條件。如果$l$和$r$間的差很小，我們可以考慮暴力枚舉直接判斷。然而，若$l<=r<=10^9$甚至更大呢？
這時往往就可以用到一種dp方式：數(shù)位dp。
?
二、做法：
這里先放一道例題：1026: [SCOI2009]windy數(shù)。
題意：求在區(qū)間$[l,r]$內(nèi)，滿足相鄰數(shù)位的差>=2的整數(shù)的個數(shù)。
首先我們可以發(fā)現(xiàn)，$[l,r]$的答案=$[1,r]$的答案-$[1,l)$的答案。于是我們可以把問題轉(zhuǎn)化為求$[1,r]$和$[1,l-1]$的答案。因?yàn)?l<=r<=2*10^9$，所以暴力枚舉肯定行不通。但是我們可以發(fā)現(xiàn)這道題中整數(shù)需滿足的條件只與相鄰數(shù)位有關(guān)，這啟示我們，也許可以按位dp？
我們先來看一張經(jīng)典的圖（表示區(qū)間$[0,22]$）：
?
這幅圖中把正整數(shù)按位用樹的形式表示，那么區(qū)間$[0,x]$（這里x=22）就可以拆成多棵滿10叉樹（即圖中的藍(lán)圈），而且因?yàn)槊繉铀玫臉鋫€數(shù)不會超過10棵（0~9），總共有$\log_{10}{x}$層，則樹的個數(shù)規(guī)模為$O(10\log{x})$。
那么單棵滿10叉樹的答案怎么求呢？我們仔細(xì)觀察這棵樹，那么就可以發(fā)現(xiàn)每棵滿10叉樹表示的數(shù)是位數(shù)相同（等于它從下往上數(shù)所處的層數(shù)），最高位相同（等于根節(jié)點(diǎn)表示的數(shù)），且該樹的答案只與以樹根的10個兒子為根的，10棵子樹的答案有關(guān)。并且在整棵樹中，處在同一層的，且子樹根節(jié)點(diǎn)表示的數(shù)相同的樹（即位數(shù)相同，最高位相同），它們是等價的。于是我們就可以直接設(shè)$f[i][j]$表示有i位，最高位為j的滿足條件的整數(shù)的個數(shù)，然后xjb轉(zhuǎn)移。于是就可以優(yōu)哉游哉地dp， 然后按圖統(tǒng)計(jì)答案了。
不過這道題還是比較麻煩，因?yàn)樾枰懦皩?dǎo)零的影響，不過核心思想還是上面的那樣，然后再分位數(shù)統(tǒng)計(jì)就好了。
代碼（時間復(fù)雜度$O(10^2\log{r})$）：
#include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> #include<algorithm> #include<queue> #include<vector> #include<map> #define ll long long #define ull unsigned long long #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define lowbit(x) (x& -x) #define mod 1000000007 #define inf 0x3f3f3f3f #define eps 1e-18 #define maxn 100020 inline ll read(){ll tmp=0; char c=getchar(),f=1; for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1; for(;'0'<=c&&c<='9';c=getchar())tmp=(tmp<<3)+(tmp<<1)+c-'0'; return tmp*f;} inline ll power(ll a,ll b){ll ans=0; for(;b;b>>=1){if(b&1)ans=ans*a%mod; a=a*a%mod;} return ans;} inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;} using namespace std; int f[20][10]; int l,r; int dp(int x) {int num[20],len=0;for(;x;x/=10)num[++len]=x%10;for(int i=0;i<=9;i++)f[1][i]=1;//預(yù)處理 for(int i=2;i<=len;i++)for(int j=0;j<=9;j++){f[i][j]=0;for(int k=0;k<=9;k++)if(abs(j-k)>=2)f[i][j]+=f[i-1][k];}//處理f數(shù)組，f[i][j]表示有i位,最高位為j的的windy數(shù)個數(shù)*/ int ans=0;for(int i=1;i<len;i++)for(int j=1;j<=9;j++)ans+=f[i][j];//統(tǒng)計(jì)位數(shù)小于len的數(shù)一定小于n，直接加上 for(int i=len;i;i--){int l=(i==len)?1:0,r=(i==1)?num[i]:num[i]-1;//不含前導(dǎo)零，所以最高位不能取0，從1開始枚舉，否則從0開始//除個位以外，因當(dāng)前位若取num[i]可能超出1~n的范圍，所以只能取到num[i]-1；因?yàn)樵儐?~n時包含n，所以個位的上限要取num[i]for(int j=l;j<=r;j++)if(i==len||abs(j-num[i+1])>=2)ans+=f[i][j];if(i<len&&abs(num[i]-num[i+1])<2)break;//統(tǒng)計(jì)下一位時，這一位取的是num[i]，若會和上一位num[i+1]發(fā)生沖突，則不可能出現(xiàn)windy數(shù)，直接break掉 }return ans; } int main() {l=read(); r=read();printf("%d\n",dp(r)-dp(l-1)); } bzoj1026?
?
三、歸納：
數(shù)位dp的特征：數(shù)據(jù)規(guī)模大，統(tǒng)計(jì)整數(shù)個數(shù)，被統(tǒng)計(jì)的數(shù)滿足的條件往往與數(shù)位之間的關(guān)系或數(shù)位間的運(yùn)算有關(guān)。
基本做法：差分，先按位dp出所需數(shù)據(jù)（$f[i][S]$->i位數(shù)，狀態(tài)為S），然后再拆分原區(qū)間，用dp出的數(shù)據(jù)統(tǒng)計(jì)。
?
?
四、其他例題：
1、【bzoj1833】[ZJOI2010] count 數(shù)字計(jì)數(shù)
裸的數(shù)位dp，分別計(jì)算每個數(shù)字出現(xiàn)的次數(shù)，做法和上面類似。
代碼：
#include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> #define ll long long #define ull unsigned long long #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define lowbit(x) (x& -x) #define mod 1000000007 #define inf 0x3f3f3f3f #define eps 1e-18 #define maxn 100010 inline ll read(){ll tmp=0; char c=getchar(),f=1; for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1; for(;'0'<=c&&c<='9';c=getchar())tmp=(tmp<<3)+(tmp<<1)+c-'0'; return tmp*f;} inline ll power(ll a,ll b){ll ans=1; for(;b;b>>=1){if(b&1)ans=ans*a%mod; a=a*a%mod;} return ans;} inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;} using namespace std; ll f[20][10][10],base[20]; ll l,r; void prework() {base[0]=1;for(int i=1;i<=13;i++)base[i]=base[i-1]*10;for(int i=0;i<=9;i++)f[1][i][i]=1;for(int i=2;i<=13;i++)for(int j=0;j<=9;j++){ll x=f[i-1][0][0]+f[i-1][0][1]*9;for(int k=0;k<=9;k++){f[i][j][k]=(j==k?base[i-1]:0)+x;}} } ll solve(ll n,int num) {if(n<0)return 0;ll tmp=++n;//這里++n是為了把閉區(qū)間轉(zhuǎn)化為開區(qū)間，因?yàn)橄旅媲蠼鈺r1~n的答案并不包括n。。int a[20],len=0;for(;tmp;tmp/=10)a[++len]=tmp%10;for(int i=1;i<len;i++)for(int j=1;j<=9;j++)ans+=f[i][j][num];for(int i=len;i;i--){for(int j=(i==len?1:0);j<a[i];j++)ans+=f[i][j][num];n-=a[i]*base[i-1];if(a[i]==num)ans+=n;}return ans; } int main() {prework();l=read(); r=read();for(int i=0;i<9;i++)printf("%lld ",solve(r,i)-solve(l-1,i));printf("%lld\n",solve(r,9)-solve(l-1,9)); } bzoj1833?
轉(zhuǎn)載于:https://www.cnblogs.com/quzhizhou/p/9245648.html
總結(jié)
- 上一篇： 死磕算法之快速排序
- 下一篇： for循环数据量太大_中文文本分类rob