(待完成)qbxt2019.05 總結2 - 數位DP

數位 DP 嚴格來說其實并不是 DP……它只是個單純的計數問題

但是怎么說呢……現在大家似乎都把數位 DP 叫這個名字，所以……我們還是……叫它 DP

額什么是數位 DP 呢？

一句話概括——一類求在 K 進制下m滿足條件的數的數量有多少個的算法

常見的問題形式：

求 [l..r] 之間的在 K 進制下滿足條件 F 的數有多少個？

什么？你說for (int i = l ; i <= r; i++) ans+=check(i);？

別學競賽了，回家養鯤吧

我們很快就會發現，數位 DP 的復雜度和位數相關，所以一般數據規模奇大

（以上摘自lyd課件）

數位DP

（以下基于k進制討論）

數位DP一般會讓你求\([l,r]\)滿足條件的個數，這里我們設函數\(c(x)\)表示小于x的正整數中滿足條件的個數，則最終答案就是 \(c(r+1)-c(l)\) 。但k進制時加一操作不一定好實現，所以更常用的是 \(c(r)-c(l)+\text{對r的特判結果}\)。

所以問題轉化為求\(c(x)\)。

正如它名字中的“數位”，DP狀態的第一維通常是數字的位數。所以只要寫出轉移方程，就可以得到小于\(k^x\)的滿足條件的個數（其中x是任意/給定正整數）即\(\sum dp[x][...]\)

現在要求\(c(x)\)。設\(x\)有\(l\)位，且現在已經求得了\(dp[l-1][...]\)。現在考慮最高位，分為兩種不同的情況：

1. 滿足條件的y的最高位小于x的最高位。這時能保證\(y<x\)，所以后面任意選。

2. 滿足條件的y的最高位等于x的最高位。這時可以遞歸解決后面的位構成的子問題。但我們發現遞歸完全是浪費，因為子問題求出的dp數組是一樣的。所以在子問題中真正有用的是求情況1和遞歸下一層。

   因為遞歸的層數是遞減的，于是我們可以把遞歸改為循環。

---

上面這些抽象的描述說實話我都看不懂QAQ

考慮這樣的一道題目：求\([l,r]\)中不包含4和62的數的個數。

那么就可以設\(c(x)\)為小于\(x\)的數中不包含4和62的數的個數，最終答案即為\(c(r+1)-c(l)\)。

這里可以設\(dp[i][j]\)表示長度為i位的，最高位是j的滿足條件的數的個數。然后我們可以寫出這樣的轉移方程：\(dp[i][j](j\neq4)=sum\{dp[i-1][k]|\text{當}j=6\text{時}k\neq2\}\)

下面假設x有l位，最高位是x[1]，最低位是x[l]，其他類似。這一段代碼求出了dp數組。

for(int j=0;j<=9;j++){if(j==4)continue;dp[1][j]=1;
}
for(int i=2;i<=l;i++){for(int j=0;j<=9;j++){if(j==4)continue;for(int k=0;k<=9;k++){if(j==6&&k==2)continue;dp[i][j]+=dp[i-1][k];}}
}

然后考慮情況一。

int ans=0;
for(int j=0;j<x[1];j++){if(j==4)continue;ans+=dp[l][j];
}

然后是情況二。先寫遞歸版。（toint表示將數組表示的數字轉換成int，toarr則相反）

ans+=c(從前面去掉1位的x);

這時我們可以發現，在第一次遞歸里有用的代碼是如下的部分：

for(int j=0;j<x[2];j++){if(j==4||(j==2&&x[1]==6)continue;ans+=dp[2][j];
}
ans+=c(從前面去掉2位的x);

所以最終我們應該把代碼修改為這樣子：

int ans=0;
for(int i=l;i>=1;i--){for(int j=0;j<x[l-i+1];j++){if(j==4||(j==2&&x[l-i]==6))continue;ans+=dp[i][j];}
}