天天看點
傳回

動态規劃 | 數位 DP

動态規劃 | 數位 DP

Luogu Wisdom Engine！Uh！

章零 · 序言

在我痛斥全給我推 DP 的 Luogu Wisdom Engine 和 GP2 Engine 一樣令人 Uh 的時候，還是要看一看它到底給我推的什麼題的。

于是昨天點開了 P2602 數字計數 [ZJOI2010]，一看顯然是個數位 DP，但是我隻是單純的知道數位 DP，之前相關的題目也就隻做過 Windy 數，于是決定學一下。

然後發現數位 DP 能套模闆的題占多數，于是昨天下午 + 晚上做了好多數位 DP 題的樣子，那麼就來寫一點東西罷（

章一 · 初見

那麼什麼是數位 DP 呢（

節一 · 簡介

先放一下 OI-Wiki 上的數位介紹：

數位：把一個數字按照個、十、百、千等等一位一位地拆開，關注它每一位上的數字。如果拆的是十進制數，那麼每一位數字都是 0~9，其他進制可類比十進制。​​[1]​​

因為是國小知識是以就不多做解釋。

那麼數位和 DP 是什麼我們都知道了，那麼數位 DP 就是針對一些可以用數位的思想去解的題目，而這些題目通常會有非常明顯的特征。

節二 · 題目特征

一般來說數位 DP 的題目有如下特征：

  1. 題目所求和數位相關或是轉化後和數位相關，比如求一個數每一位的和；
  2. 一般是一個計數問題；
  3. 資料範圍很大，所統計的答案已經與資料大小無關；
  4. 一般輸入時給出的是一個區間。

簡單來說就是，在區間 \([l,r]\) 中統計符合條件 \(P(i)\) 的數 \(i\) 的個數，一般 \(P(i)\) 和 \(i\) 的大小無關，而與 \(i\) 的數位組成有關。

既然和 \(i\) 的大小一般無關了，是以數位 DP 的複雜度就和 \(i\) 的大小關系不大了。

章二 · 模闆

衆所周知數位 DP 的模闆是非常好套的，于是先來講一講模闆罷。

當然好套隻是其中一個原因，之是以先講，是覺得先看完了模闆架構和狀态設計之後，更容易了解數位 DP 的過程。

節一 · 設計狀态

我這裡用記憶化搜尋的形式來轉移狀态，這樣的好處是我們的思維量更少，可以在 \(DFS\) 函數裡維護更多的資訊。

當然模闆也更好套，更好背

下面的參數不懂可以先不用着急，下面節二會稍作分析。

條一 · DFS 函數

那麼我們先來看一看 \(DFS\) 中都需要什麼參數：

  1. \(\texttt{lead}\)：前導 \(0\) 的狀态；
  2. \(\texttt{limit}\)：目前位置做多取值的有沒有被限制；
  3. \(\texttt{pos}\)：目前的狀态在原數中的位置；
  4. \(\texttt{st}\)：目前狀态的答案；
  5. \(\texttt{pre}\)：上一位數字。
  6. \(\cdots\)

當然以上參數不一定每個題都需要，視題目而定即可。

當然你記錄的東西多了一般也不會錯

條二 · DP 數組

下文中的 DP 數組我都用 \(f(i,j,\cdots)\) 來表示。

一般來說我們要在 DP 數組中記錄目前狀态在原數中的位置 \(\texttt{pos}\) 和目前狀态的答案 \(st\)，也就是說，對于簡單的數位 DP，方程的樣子一般都是 \(f(\texttt{pos},\texttt{st})\)。

當然根據題目的不同還有可能會往裡面加一些其他的東西。

節二 · 參數分析

前面所說的參數可能初見會不懂，于是下面來稍作分析。

下文中若無特殊說明，\(a_{pos}\) 均表示原數第 \(pos\) 位的數。

條一 · lead

這個參數的存在是為了我們要從最高位開始搜時避免一些不必要的錯誤。

下面來舉個例子：

求 \([l,r]\) 中有任意相鄰兩位相同的數字。

當 \(l=1,r=10000\) 時，顯然 \(11,111,444,555,1111,4444\) 都是符合題意的數字。

但是我們搜尋時記錄出來的上列數字是這樣的：\(00011,00111,00444,00555,01111,04444\)，顯然有了前導 \(0\) 之後這些數字都不滿足題意了，于是我們要把前導 \(0\) 的影響去掉。

這個标記的意義如下：

  1. \(\texttt{lead} = 0 \to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{newst},\cdots)\)
  2. \(\texttt{lead} = 1 \begin{cases} a_{pos} = 0 &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{st},\cdots) \\ a_{pos} \ne 0 &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{newst},\cdots)\end{cases}\)

但是顯然當我們所統計的東西和上一位是否為 \(0\) 無關的時候，這個參數也可以不用記錄（比如問一個數的組成）。

條二 · limit

這個參數如果用相對嚴謹的形式去一句話定義的話會很繞，但是舉個例子會非常有助于了解。

從範圍 \([0,114514]\) 中找符合條件 \(P(i)\) 的數 \(i\)。

如果我們目前搜尋到的數字的最高位為 \(1\)，那麼顯然我們次高位搜尋的範圍會被限制為 \([0,1]\)。

同理，當我們搜尋到第 \(i\) 位的時候，若第 \(i-1\) 位達到了其限制，那麼目前位置的搜尋範圍就由 \([0,9]\) 被限制到了 \([0,a_{pos}]\)。

為了區分目前位置有沒有被限制，我們加入了參數 \(\texttt{limit}\)。

這個參數意義如下：

我們設 \(i\) 為我們在目前位上搜尋到了 \(i\)，那麼顯然 \(i\in[0,9] \operatorname{or} i\in[0,a_pos]\)，為了友善，下面統一将可搜的數的最大值設為 \(up\)。

在這裡 \(DFS\) 函數第二個參數為 \(\texttt{limit}\)。

  1. \(\texttt{limit} = 0 \to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},0,\cdots)\)
  2. \(\texttt{limit} = 1 \begin{cases} i < up &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},0,\cdots) \\ i = up &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},1,\cdots)\end{cases}\)

節三 · DP 數組

使用記憶化的原因很簡單：數位 DP 過程中存在大量的重複狀态，采取記憶化就可以有效的降低複雜度。

但是有時候一些狀态并不能記錄，也就是目前狀态存在限制的時候不能取用之前的狀态或将本次 DFS 結果存儲在 DP 數組中。

一般來說即為 \(\texttt{limit} = 1\) 時顯然不能取用和存儲。

節四 · Code

前面對一些參數稍作分析之後，我們來上一份模闆代碼。

不過在上模闆代碼之前，先獻上我的垃圾預設源。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

template<typename J>
I void fr(J &x)
{
static short f(1);
char c=getchar();
x=0;
while(c<'0' or c>'9')
    {
if(c=='-') f=-1;
c=getchar();
    }
while (c>='0' and c<='9') 
    {
x=(x<<3)+(x<<1)+(c^=48);
c=getchar();
    }
x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
x<0?x=-x,putchar('-'):1;
static short stak[35],top(0);
do
    {
stak[top++]=x%10;
x/=10;
    }
while(x);
while(top) putchar(stak[--top]+'0');
k?puts(""):putchar(' ');
}

然後就是模闆代碼。

LL DFS(bool limit,int st,int pos,...)
{
if(!pos and ...) Heriko st;
if(!limit and f[pos][st]...[...]!=-1 and ...) Heriko f[pos][st]...[...];
int res(0),up(limit?a[pos]:9);
for(R int i(0);i<=up;++i) res+=DFS(...);
if(!limit and ...) f[pos][st]...[...]=res;
Heriko res;
}

I LL DP(LL x)
{
mst(f,-1);
int len(0);
while(x) a[++len]=x%10,x/=10;
Heriko DFS(1,0,len);
}

S main()
{
fr(l),fr(r);
fw((DP(r)-DP(l-1)+MOD)%MOD,1);
Heriko Deltana;
}

章三 · 例題

如果你能看懂模闆，那麼下面這道題你能很容易的切掉。

​​LOJ | #10169.數字計數​​

​​洛谷 | P2602 數字計數 [ZJOI2007]​​ [提高+/省選-]

給定兩個正整數 \(a\) 和 \(b\)，求在 \([a,b]\) 中的所有整數中，每個數位(digit)各出現了多少次。

節一 · 思路

是一道數位 DP 的闆子題，正好遇上洛谷日爆（

采用模闆化的 DFS 做法，定義 \(f\) 數組如下 \(f(i,j)\) 表示是從高到低第 \(i\) 位，\(j\) 則是數字出現次數。

DFS 函數為 \(DFS(pos,num,ans,lead,limit)\)，參數分别表示：從高到低第幾位，要求哪個數出現的次數，目前出現次數，前導零的狀态，目前位置上限的狀态。

節二 · Code 

CI MXX=15;

LL l,r,f[MXX][MXX],a[MXX];

LL DFS(LL pos,LL num,LL st,bool lead,bool limit)
{
if(!pos) Heriko st;
if(!limit and lead and f[pos][st]!=-1) Heriko f[pos][st];
LL n(limit?a[pos]:9),res(0);
for(R LL i(0);i<=n;++i) res+=DFS(pos-1,num,st+((i or lead) and (i==num)),(lead or i),((i==n) and limit));
if(!limit and lead) f[pos][st]=res;
Heriko res;
}

I LL DP(LL x,LL y)
{
mst(f,-1);LL len(0);
while(x)
    {
a[++len]=x%10;
x/=10;
    }
Heriko DFS(len,y,0,0,1);
}

S main()
{
fr(l),fr(r);
for(R LL i(0);i<=9;++i) fw(DP(r,i)-DP(l-1,i),0);
Heriko Deltana;
}
數位 #define 數組 搜尋 #include
上一篇: 擺花 （DP動态規劃）
下一篇: 動态規劃之插頭DP入門

繼續閱讀