序
天堂在左虱而，戰(zhàn)士向右
引言
數(shù)位DP在競(jìng)賽中的出現(xiàn)幾率極低痹筛，但是如果不會(huì)數(shù)位DP氨肌，一旦考到就只能暴力騙分鸿秆。
以下是數(shù)位DP詳解，涉及到的例題有：
- [HDU2089]不要62
- [HDU3652]B-number
概述
首先我們要理清的是怎囚，到底數(shù)位DP是什么卿叽。
事實(shí)上，一般數(shù)位DP的題目題面描述都會(huì)有以下內(nèi)容：
- 求出一段區(qū)間
中恳守，滿足某一特殊條件的數(shù)有多少個(gè)
在例題1 不要62中考婴，特殊條件是數(shù)中不能出現(xiàn)"62"；在例題2 B-number中催烘，特殊條件是數(shù)中出現(xiàn)了13且該數(shù)可以被13整除沥阱；
一般題目中的數(shù)據(jù)范圍會(huì)使得
超時(shí)。因此伊群，直接遍歷將無(wú)法拿到全分考杉。而數(shù)位DP則是在范圍內(nèi)按位遞推出最大值的快捷算法。以例題2 B-number中的數(shù)位DP為例：
足以顯示出數(shù)位DP的優(yōu)越性舰始。
主要實(shí)現(xiàn)
由于DP的本質(zhì)就是記憶化搜索崇棠，我們通過(guò)記憶化搜索的方式實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃。這種方式相比正面遞推丸卷，在大多數(shù)情況下要簡(jiǎn)介一些枕稀。
一、搜索過(guò)程
以例題1 不要62為例谜嫉。
首先萎坷，我們需要定義以下基本的變量與函數(shù)，它們是在所有數(shù)位DP中通用的：
int digit[maxn];
int dfs(int len,int fp,int str){
}
其中沐兰，表示一個(gè)數(shù)在所有數(shù)位都取最大值的情況下哆档，第
位的最大值。
而dfs函數(shù)中的表示當(dāng)前層我們還需處理多少數(shù)位僧鲁。當(dāng)
的值為
時(shí)虐呻，則代表我們已經(jīng)處理到了最低位。
fp則代表當(dāng)前數(shù)位是否受到最高位的限制寞秃。舉個(gè)例子斟叼，我們規(guī)定在一次運(yùn)算中的值為
。此時(shí)我們已經(jīng)計(jì)算到了第2位春寿。若前一位為
朗涩，則這一位最大也只能取
，否則會(huì)超出
的限制绑改，此時(shí)fp的值為1谢床；若前一位小于
兄一，則當(dāng)前位不受最高位的限制，我們可以取任意數(shù)字识腿，則此時(shí)fp的值為0出革。
str則代表當(dāng)前狀態(tài)，我們稍后再做解釋渡讼。
這時(shí)骂束，我們分析題面，發(fā)現(xiàn)：
- 限制條件只有一個(gè)成箫，即不能出現(xiàn)62
因此展箱，我們可以將這一限制條件填入已經(jīng)設(shè)出的狀態(tài)中。當(dāng)之前的數(shù)位中已經(jīng)出現(xiàn)了62蹬昌，我們就使其為1混驰，否則我們使其為0。
這時(shí)皂贩，根據(jù)這一條件栖榨，就可以設(shè)出DP數(shù)組了
int dp[maxn][100];//表示在處理到第i位、之前的數(shù)位中出現(xiàn)/未出現(xiàn)62使的方案數(shù)先紫。
不過(guò)此時(shí)治泥，我們會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題：如果上一位出現(xiàn)了6，而是否出現(xiàn)62由當(dāng)前位決定時(shí)遮精，怎么辦呢居夹？因此，我們要對(duì)的定義稍作更改本冲。
我們令表示：若上一位出現(xiàn)了
准脂，則
;若已經(jīng)出現(xiàn)了
，則
檬洞；否則
狸膏。
此時(shí)，我們已經(jīng)可以通過(guò)定義寫下判斷狀態(tài)的子函數(shù)了添怔。
int check(int str,int i){
if(str==0){
if(i==6)return 1;
return 0;
}
else if(str==6){
if(i==6)return 1;
if(i==2)return 2;
return 0;
}
return 2;
}
回過(guò)頭來(lái)湾戳，我們?cè)賮?lái)繼續(xù)完成dfs函數(shù)。
首先广料，寫下當(dāng)我們搜索到最后一位時(shí)的返回操作與記憶化搜索的返回操作砾脑。
int digit[maxn];
int dfs(int len,int fp,int str){
if(len==-1)return str==2;
if(!fp && dp[len][str])return dp[len][str];
//條件中的!fp是對(duì)[l,r]取開區(qū)間。
}
接下來(lái)我們要做的是判斷當(dāng)前狀態(tài)下我們能取到的最大數(shù)位艾杏。
int fpmax=fp?digit[len]:9;
接著我們?cè)俦闅v搜索下一個(gè)數(shù)位韧衣，并返回答案。
int ret=0;//返回值
for(register int i=0;i<=fpmax;i++){
ret+=dfs(len-1,fp && i==fpmax ,check(str,i));
}
return dp[len][str]=ret;
整個(gè)子函數(shù)的代碼如下：
int dfs(int len,int fp,int str){
if(len==-1)return str==2;
if(!fp && ~dp[len][str])return dp[len][str];
int fpmax=fp?digit[len]:9,ret=0;
for(register int i=0;i<=fpmax;i++){
ret+=dfs(len-1,fp && i==fpmax,check(str,i));
}
return dp[len][str][rel]=ret;
}
而例題1 不要62的代碼如下：
#include<bits/stdc++.h>
#define int long long
//#define local
using namespace std;
int dp[100][200][100],digit[100];
int check(int str,int i){
if(str==0){
if(i==6)return 1;
return 0;
}
else if(str==6){
if(i==6)return 1;
if(i==2)return 2;
return 0;
}
return 2;
}
int dfs(int len,int fp,int str){
if(len==-1)return str==2;
if(!fp && ~dp[len][str])return dp[len][str];
int fpmax=fp?digit[len]:9,ret=0;
for(register int i=0;i<=fpmax;i++){
ret+=dfs(len-1,fp && i==fpmax,check(str,i));
}
return dp[len][str][rel]=ret;
}
int f(int n){
int len=0;
while(n){
digit[len++]=n%10;
n/=10;
}
return dfs(len-1,1,0);
}
signed main(){
#ifdef local
freopen("1.txt","r",stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int a,b;
memset(dp,-1,sizeof(dp));
while(cin>>b>>a){
//cout<<"-->"<<b<<endl;
printf("%d\n",f(b)-f(a-1));
}
//cout<<f(1000)<<endl;
return 0;
}
注意，在f函數(shù)中畅铭，可以看到我們首次dfs的代碼是
dfs(len-1,1,0);
為什么的值為總長(zhǎng)度-1氏淑，而不是總長(zhǎng)度本身呢？
因?yàn)檫@樣我們處理到最后時(shí)而不是
換句話說(shuō)硕噩，只是筆者的習(xí)慣而已233333
細(xì)節(jié)-關(guān)于狀態(tài)
事實(shí)上假残，不是所有時(shí)候DP數(shù)組都只用開二維。
在很多時(shí)候榴徐，我們都要在dfs函數(shù)中同時(shí)記錄我們當(dāng)前處理到的數(shù)是多少守问，例如例題2 B-number匀归。
在這道題中坑资，我們要處理我們記錄的數(shù)是否能被13整除，因此我們要對(duì)DP數(shù)組作一點(diǎn)小小的微調(diào)穆端。
int dp[maxn][5][20];
多出來(lái)的一維用于記錄計(jì)算出來(lái)的數(shù)對(duì)13取模后的值袱贮。不記錄其本身是因?yàn)榭臻g限制，且失去了數(shù)位DP的優(yōu)越性体啰。
對(duì)于dfs中所處理的數(shù)的記錄攒巍，不難想到用這樣的方法：
int dfs(int len,int fp,int str,int rel){
for(register int i=1;i<=9;i++)dfs(len-1,fp && i==digit[i],check(str,i),rel*10+i);
}
因此，對(duì)于例題2 B-number荒勇，我們的完整代碼變成了這樣：
#include<bits/stdc++.h>
#define int long long
//#define local
using namespace std;
int dp[100][200][100],digit[100];
int check(int str,int i){//返回:0-->什么都沒(méi)有柒莉，1-->已出現(xiàn)過(guò)1，2-->已出現(xiàn)過(guò)13
if(str==0){
if(i==1)return 1;
return 0;
}
else if(str==1){
if(i==1)return 1;
if(i==3)return 2;
return 0;
}
return 2;
}
int dfs(int len,int fp,int rel,int str){
if(len==-1)return rel==0&&str==2;
if(!fp && ~dp[len][str][rel])return dp[len][str][rel];
int fpmax=fp?digit[len]:9,ret=0;
for(register int i=0;i<=fpmax;i++){
ret+=dfs(len-1,fp&&i==fpmax,(rel*10+i)%13,check(str,i));
}
return fp?ret:dp[len][str][rel]=ret;
}
int f(int n){
int len=0;
while(n){
digit[len++]=n%10;
n/=10;
}
return dfs(len-1,1,0,0);
}
signed main(){
#ifdef local
freopen("1.txt","r",stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int b;
memset(dp,-1,sizeof(dp));
while(cin>>b){
//cout<<"-->"<<b<<endl;
printf("%d\n",f(b));
}
//cout<<f(1000)<<endl;
return 0;
}
后記
數(shù)位dp雖然大多在套模板沽翔，但是里面的判斷和細(xì)節(jié)還是很多的兢孝，多寫幾道數(shù)位dp之后才能發(fā)現(xiàn)其中的規(guī)律，完全將其掌握仅偎。
