淺談 數位dp
什么是數位dp
假如你遇到一道題，其曰：“試求一個范圍 [x,y]，求這個范圍內的所有數中，每一位上的數字滿足...條件的數的個數，”這是數位dp的一般問題，這類問題的主要特點就是在數位上操作，進行計數，面對這種問題，我們就用到了數位dp.
以眼還眼
這類題的困難之處就是在數位上，那我們就見招拆招，在數位上dp，直接按照他的要求構造出一個在這個區間內的數，比如他要求我們相鄰兩位上的值必須相差2，區間為[2000,5000],那我們就構造出2424這么個數，它符合要求，因此ans++.這就是數位dp的思想了，
記憶化搜索
由于題目比較單一，所以一般就采用記憶化搜索的方式取代dp，以求簡便與易思考，我們就從一道原題來講解：luoguP2657 [SCOI2009] windy 數（模板）
題目描述
不含前導零且相鄰兩個數字之差至少為 2 的正整數被稱為 windy 數，windy 想知道，在 a 和 b之間，包括 a 和 b ，總共有多少個 windy 數？
決議
變數定義：
| 變數名 | 意義 |
|---|---|
| pos | 當前dp到數位上第幾位 |
| last | 上一位數位上的值 |
| limit | 當前位上能取的最大值 |
| lead | 前面的幾位是否都為0（前導0） |
| dp | 有多少符合要求的數字 |
| num | 極限數字每一位上的數字 |
我們的操作相當于給每一位上“空投”數字，既然是填數，那么如果我們還要滿足上下界的話，那就實在是太麻煩了，不如我們用容斥原理，將區間范圍分為[0,left-1]和[0,right],分別求這兩個區間中滿足條件的數的個數，然后用后式的回傳值減去前式的回傳值即可，
int main(){
scanf("%lld%lld",&a,&b);
ll ans1=work(a-1);//區間一
ll ans2=work(b);//區間二
printf("%lld",ans2-ans1);
return 0;
}
那么我們要處理一下每個區間，首先我們要將一個區間的最大值給分離成一個數串，其目的就是防止我們在填數的程序中一不小心就超過我們規定的范圍了，
inline ll work(ll nums){
memset(dp,-1,sizeof(dp));
ll len=0,p=nums;
while(p){//將每一個數分離出來
num[len++]=p%10;
p/=10;
}
reverse(num,num+len);//反轉，高位在前，低位在后
return dfs(0,0,len,1,1);//記憶化
}
接下來就是記憶化搜索的程序了，我們想想我們要干啥來著？1.保證我們填的數不會超過區間，2.保證我們填的數與相鄰的數的差值不小于2，3.對于有前導零的數單獨判斷，我們一個一個慢慢解決，
保證不超過區間
由于左最值最小為0，所以沒有什么關系,反而是最大值要規范一下，我們在前面有一個操作是將最大值的每一位都分離出來，其實這個操作就是在規范最大值了，我們將其每一位的值都分離出來，規定：假如前面填的數頂到了上界，那么這一位能填的數必須小于當前位的上界，上界就是我們處理出來的num陣列，之所以有個limit是因為如果前一位沒有頂到上界，那么這個位就可以隨便填，
差值不小于2
我們在列舉下一位要填的數時，強迫自己滿足條件就可以了，
前導零問題
如果一個數有前導零，說明這個數的位數沒有頂到上界（沒有達到最大值的位數），那就說明當前位隨便填都沒關系，
以上問題都解決完時，就是上代碼時間了，
code
ll dp[Maxn][Maxn][Maxn][Maxn];
ll a,b,num[Maxn];
inline ll dfs(ll pos,ll last,ll len,ll limit,ll lead){
if(pos==len) //假如位數能順利到達最后一位，那就說明我們填出來的數是滿足條件的
return 1;
if(dp[pos][last][limit][lead]!=-1)//記憶化
return dp[pos][last][limit][lead];
ll numax=9;
if(limit) //前一位頂到上界了
numax=num[pos];//那么我們能取的最大數就是最大值的當前位
ll ans=0;
for(int i=0;i<=numax;i++){//列舉能填的數
if(lead){//有前導0
if(i==0)//如果我們要在這里填0
ans+=dfs(pos+1,i,len,limit&(i==numax),1);//那就說明下一位還是要考慮前導零問題
else//反之不然
ans+=dfs(pos+1,i,len,limit&(i==numax),0);
}else{
if(abs(i-last)>=2){//必須滿足條件
ans+=dfs(pos+1,i,len,limit&(i==numax),0);
}
}
}
return dp[pos][last][limit][lead]=ans;
}
以上就是對于數位dp的全部講解了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301650.html
標籤：其他