DP 計數 機率
Introduction to Competitive Programming
- Classic DP Problems
- 二進制分解
- 01背包 vs 無限背包 vs 有限背包
- 單調隊列 / 凸包優化
- p-median problem
- Counting DP
- 爬樓梯
- 走方格的路徑數
- Combination
- 排列 - 組合
- 二項式定理 (Binomial theorem)
- Probabilistic DP
- 骰子
- 抓老鼠例題
二進制分解
其實每種物品有 \(K\) 個，不需要 \(K\) 種組合 \((1\sim K)\) 都做一次
我們只需要做 \(\lfloor \log K \rfloor\) 次就好
分別捆成 1個、2個、4個、8個、16個、…、\(2^{\lfloor \log K \rfloor}\)
以及剩下的 (\(K -1 -2 -4 ... -2^{\lfloor\log K\rfloor}\)) 這是一個
這些捆的組合，就可以湊出數量 \(1\sim k\) 的所有物品
以數量為 9 為例
分成 1, 2, 4, 2 四堆
1=1 2=2 3=1+2
4=4 5=1+4 6=2+4
7=1+2+4 8=2+4+2 9=1+2+4+2
\(K\) 個物品，拆成 \(log K\) 個
vector<int> item;
for(int i = 1; k>=i; i*=2){
item.push_back(i);
k -= i;
}
if (k) item.push_back(k);
01 背包 vs 無限背包 vs 有限背包
每個背包都有一個耐重上限 \(weight\) , 求在這個 \(weight\) 裡最多可以裝多少 \(value\) 的內容物
而對於 \(dp[i]\) 的定義則是在耐重上限為 \(i\) 的時候，可以裝的最大內容物價值為何。
01 背包 : 每個物品只能選擇取或是不取
無限背包 : 每個物品都有無限個，可以取到死
有限背包 : 每個物品各自有 \(K\) 個 依照題目給定
01背包
之前已經有教過例題了 詳情請看 背包問題
而0/1背包的實作代碼大略會長成這樣
for (int i = 1; i <= cnt; i++) //幾個物品
for (int j = weight; j >= w[i]; j--) //從物品耐重上限枚舉到此物品的重量，代表每個都最多選一次
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
無限背包
之前作業有出過 可以去補一下
完全背包模型與 0/1 背包類似，與 0/1 背包的區別僅在於一個物品可以選取無限次，而非僅能選取一次。
於是與 0/1 背包在代碼上的差別就是，枚舉重量的時候不能從最大耐重枚舉回來，而是要從最小開始，因為這樣才會有讓物品被重複選取的機會。
而無限背包的實作代碼大略會長成這樣
for(int i = 1; i <= cnt; i++)
for(int j = w[i]; j <= weight; j++)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
有限背包(多重背包)
多重背包也是 0/1 背包的一個變式。與 0/1 背包的區別在於每種物品有 \(k_i\) 個，而非一個。
一個很簡單的想法就是：把「每種物品選 \(k_i\) 次」等價轉換為「有 \(k_i\) 個物品，每個物品選一次」。這樣就可以轉換成 0/1 背包模型
然後套用 0/1 背包即可解。
但會發現一件事情，你會發現 0/1 背包的複雜度 \(O(NW)\) 在有限背包會直接變成 \(O(NWK)\) ，因此很明顯有些情況會超時，而且 \(O(NW)\) 就是神聖且不可優化的一部份，所以我們只能想辦法優化 \(K\) ，那就會需要剛剛所提到的二進制拆分。
把每個 \(K\) 做二進制拆解，那時間複雜度就會從 \(O(NWK)\) 下降成 \(O(W \cdot \sum_{i=1}^n log_2 k_i)\Rightarrow O(N \cdot W \cdot log_2 k)\)
把有限背包二進制拆分的具體代碼
index = 0;
for (int i = 1; i <= m; i++) {
int c = 1, p, h, k;
cin >> p >> h >> k;
while (k > c) {
k -= c;
list[++index].w = c * p;
list[index].v = c * h;
c *= 2;
}
list[++index].w = p * k;
list[index].v = h * k;
}
然後再去做0/1背包即可
另外還有一種是混合背包，每一種物品可能是只有一個，有 \(K\) 個，或者是有無限個，那其實也不用被這種類型的題目嚇到，只需要這樣做即可。
for (循環物品種類) {
if (是 0 / 1 背包)
套 0 / 1 背包代碼;
else if (是無限背包)
套無限背包代碼;
else if (是有限背包)
套有限背包代碼;
}
| \(\texttt{種類}\) | \(\texttt{時間複雜度}\) | \(\texttt{空間複雜度}\) | \(\texttt{狀態轉移式}\) | \(\texttt{順序以及步驟}\) |
|---|---|---|---|---|
| 0/1背包 | \(NW\) | \(N+W\) | \(\texttt{max(dp[j],dp[j-w[i]]+v[i])}\) | 從 \(W\) ~\(w_i\) |
| 無限背包 | \(NW\) | \(N+W\) | \(\texttt{max(dp[j],dp[j-w[i]]+v[i])}\) | 從 \(w_i\) ~\(W\) |
| 有限背包 | \(NWlogk\) | \(N log K + W\) | \(\texttt{max(dp[j],dp[j-w[i]]+v[i])}\) | 二進制拆分後從 \(W\) ~\(w_i\) |
單調性質 (Monotonicity)
函數單調性
函數單調性也叫做函數的遞增遞減性，分成遞增函數，遞減函數，
若\(f : X \rightarrow Y\) ，滿足對於任何 \(x_1\) \(\neq\) \(x_2\)，\(x_1, x_2 \in X\) 有 \(x_1\) < \(x_2\)
則 \(f(x_1) > f(x_2) / f(x_1) > f(x_2)\)
隊列
元素只能從頭部和尾部進行操作
單調隊列優化
單調隊列優化的技巧主要用在取極值這個動作。有時候我們必須針對一個序列的好幾個區段。此優化的是利用查詢的左界 \(L\) 與右界 \(R\) 只需要單調遞增之特性。藉此可開始推知：
- 某一元素從右界進入後必定只會從左界出去。
- 越左邊之元素一定會越先出去。
deque
而有一種可以左右都 pop 跟 push 的做法，叫雙向佇列(deque)
於是只需用 deque 維護有單調性的序列。
- 在加入新元素時就開始從 deque 右方 pop 元素，直到最右方的元素比新元素更極端或 Deque 已經空了，再將新元素 push 入。
- 要刪除元素時只需檢查所要刪的是否是當前 deque 最左端的元素，是即刪。查詢極值時，直接取 Deque 最左端元素之值即可
或者建立陣列
因為 deque 有可能還是會被卡 (通常不會)，如果真遇到了可以直接寫兩個陣列維護就好，然後用 head 跟 tail 指向前面跟後面，就不需要 pop 的動作，缺點是需要占很多空間。
有限背包問題
回到有限背包問題，要怎麼利用單調性質呢?
首先來看有限背包問題的關係式 定義 \(f_{i,j}\) 為前 \(i\) 個物品裝入承重為 \(j\) 的背包最大價值
\(f_{i,j} = max_{k=0}^{k_i} (f_{i-1, j-k\times w_i} + v_i \times k)\)
從這來看，應該很難看出有什麼單調性質，所以稍微做一點技巧操作 (Change Variable)
推導
\(f_{i,j} = max_{k=0}^{k_i} (f_{i-1, j-k \times w_i} + v_i \times k)\)
設 \(g_{x,y} = f_{i, x \times w_i+y}\) (\(y\) 是 \(\mod w_i\) 也就是餘數)
設 \(\tilde{g}_{x,y} = f_{i-1, x \times w_i+y}\)
則 \(g_{x,y} = f_{i, x \times w_i+y} = max_{k=0}^{k_i} (f_{i-1, (x-k) \times w_i+y} + v_i \times k)\)
\(= max_{k=0}^{k_i} (\tilde{g}_{x-k,y} + v_i \times k)\)
設 \(G_{x,y} = \tilde{g}_{x,y} - v_i \times x\)
得到 \(g_{x,y} = max_{k=0}^{k_i} (G_{x-k,y}) + v_i \times x\)
這樣就成功轉換成了一個單調形式了
實作
void solve() { // 物品數量n, 背包容量 W for (int i = 1 ; i <= n ; i++) { int v, w, m; // 價值v 重量w 數量m cin >> v >> w >> m; m = min(m, W/w); // 背包最大可以取的數量 for (int y = 0 ; y < w ; y++) { // 餘數 y int head = 1, tail = 1; // 隊列頭尾 for (int x = 0; x <= (W-y)/w ; x++) {// 推導結論+維護陣列 int G = dp[y+x*w] - x*v; while (head < tail && g[tail - 1] <= G) tail--; g[tail] = G; num[tail++] = x; while (head < tail && x-num[head] > m) head ++; dp[y+x*w] = max(dp[y+x*w], g[head] + x*v); } } } cout << dp[W] << endl; }
複雜度
\(G_{x,y}\) 可以 \(O(1)\) 計算。
\(g_{x,y}\) 需要 \(O(\frac{W}{w_i})\) 計算，所以計算全部需要 \(O(\frac{W}{w_i}) \times O(w_i) = O(W)\)
所以複雜度就降為 \(O(NW)\)
凸包優化 (Convex Hull Optimization)
(也有很多人稱斜率優化)
有些轉移形式可以寫成: \(dp(i) = min/max \{ dp(j) + \cdots + x_i \}\)
省略號中只與j有關，也就是說每個\(dp(i)\)只會多一個\(+x_i\)判斷，這種類型就可以用單調隊列優化，使時間複雜度從 \(O(n^2)\) 降為 \(O(n)\)
但如果是 \(dp(i) = min/max \{ dp(j) \times x_i \}\) 既有\(i\)相關的量和\(j\)相關的量，就沒辦法單純只考慮\(x_i\)了，所以這時候不能使用單調隊列優化。那怎麼優化呢?
(眼尖的你可以發現，單調隊列優化就是斜率優化的特殊情況 斜率 \(= 0\))
凸包優化
先考慮簡單的轉移式 \(dp(i) = a_j\times x_i + b_j\)
觀察可以發現，對於所有的 \(j\) 為 \(y = a_j x + b_j\) 的線性函數，所以\(dp(i)\) 在求的就是在這些線性函數中代入 \(x_i\) 的最大值是多少。
對於三條線型函數 \(A ,B ,C\)滿足斜率有 \(m_A < m_B < m_C\) 時，可以分類成以上兩種情況。
- 左邊這張圖: 每條線，都有在某個時刻當上最大值的時候，所以每條線都是有用的。
- 右邊這張圖: \(B\)這條線，在所有時刻都無法成為最大值，所以我們稱\(B\)為沒有用的線。
而要判斷B這條線沒有用，可以利用\(X_{AB}\) , \(X_{AC}\) 大小來判斷
如果把一堆線段中所有「沒有的線段」移除掉，可以得到如下圖:
只擷取最大值的區段，可以得到一個下面這張圖，我們稱之為「凸包」
思路
對於每條還存在的線段,都能夠找到連續的一段區間使得在這段區間代入 \(x\) 時有最大值，並且由斜率小到大這些區間會是接起來的。所以只需要維護所有最大值出現的區間，在算X的極值時，就可以用二分搜找出他在哪個區間，代入轉移式即可找出極值。
例題 (APIO 2010 Commando)
題目轉換 : 給你一個長度 N 的正整數序列 \(a_1 ∼ a_N\)，請你將區間分割成若干段,每段 \([l, r]\) 的權
重為 \((\sum_{i=l}^ra_i)^2 + C\)，試問分段後的最小權重和。
要想辦法推導出長相如 \(y = kx + b\) 的形式
推導
定義 \(dp[i]\) 是把前綴 \([1,i]\) 切段後的最小權重和 (同時定義\(S[i]\)為前綴和
所以\(dp[i] = min \{ (\sum_{k=j+1}^ia_k)^2 + C + dp[j] \}\)
\(\Rightarrow dp[i] = min \{ (S[i] - S[j])^2 + C +d[j] \}\)
\(\Rightarrow dp[i] = min \{ S[i]^2 -2S[j]S[i] + S[j]^2 + C + dp[j] \}\)
推導
提出所有跟j無關的項
\(\Rightarrow dp[i] = min \{ -2S[j]S[i] + S[j]^2 + dp[j] \} + S[i]^2 + C\)
就可以定義
\(y = dp[i]\)
\(k = S[i]\)
\(x = 2\times S[j]\)
\(b = s[j]\times s[j] + dp[j]\)
得到長相\(: y = kx + b\)，可以發現\(K\)就是斜率，B\(是\)截距
就只需要去維護\(k\)就好了
實作
斜率
double slope(ll l, ll r) { // 計算兩點斜率 y2-y1/x2-x1 return double((f[l]+s[l]*s[l]) - (f[r]+s[r]*s[r])) / (2*s[l]-2*s[r]); }
主要 (tree 是一個 set 維護，\(f\) 就是剛剛推導的 \(dp\))
tree.insert(0); f[0] = 0; // s 是前綴和 for (int i = 1 ; i <= n ; i++) { while (tree.size() > 1) { auto it = tree.begin(); it2 = it; ++it; //左極值維護 if (slope(*(it2),*(it)) <= s[i]) tree.erase(it2); else break; } ll front = *tree.begin(); f[i] = f[front] + (s[i]-s[front]) * (s[i]-s[front]) + c; while (tree.size() > 1) { auto it = tree.rbegin(); it2 = it; ++it; //右極值下凸包維護 if (slope(*(it2),*(it)) <= slope(*(it2),i)) tree.erase(*it2); else break; } tree.insert(i); }
老樣子可以先簡化問題，思考他只有一個重點，或是只有一個點的時候會發生什麼事情。
然後就會發現可以把問題簡化成
然後就會發現 p-Median Problem 就變成了如何分區的問題，只要分好區然後選擇每個區的中位數就會是對的。
\(N\) 為點個數， \(P\) 為重點個數。總共 \(O(NP)\) 個子問題，計算一個子問題需時 \(O(N)\) ，時間複雜度 \(O(N^2P)\) 。
\(dp[i][j]\) 代表當今天只有前 \(j\) 個點，有 \(i\) 個重點的時候答案是多少。
\(d[i][j]\) 各種區域，其聯絡距離的總和。
\(r[i][j]\) 記錄最佳的分界線(分區)位置。
void p_Median(){
for (int i=1; i<=N; ++i)
for (int j=i; j<=N; ++j){
m = (i+j)/2,d[i][j] = 0; // m是中位數，d[i][j]為距離的總和
for (int k=i; k<=j; ++k) d[i][j] += abs(arr[k] - arr[m]);
}
for (int p=1; p<=P; ++p)
for (int n=1; n<=N; ++n){
dp[p][n] = 1e9;
for (int k=p; k<=n; ++k)
if (dp[p-1][k-1] + d[k][n] < dp[p][n]){
dp[p][n] = dp[p-1][k-1] + d[k][n];
r[p][n] = k; // 從第k個位置往右到第j個位置
}
}
}
可用凸包加速到 \(O(NP)\)。
另外想鞏固一下知識點的可以去寫這題 HW E
他需要遞迴輸出路徑 小難
經典題目 : 二階樓梯計數問題 (有障礙物)
題目敘述 : 給定一個 \(n \times m\) 的棋盤\((1\le n,m < 10^5)\)，棋盤上有 \(N (1 ≤ N ≤ 2000)\) 個格子是黑色的，其他是白色的
初始位置在左上角，只能向下或向右移動，不能經過黑色格子
從左上角移動到右下角一用有多少種走法？
跟二階樓梯一模一樣，只是多了障礙物不能走到。
可以發現，若不考慮黑格子(沒有黑格子)，則可以寫出
\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\)
然後其實就相當於 \(C_{m}^{m+n}\) (每列要選擇要走哪一格，並且只能相鄰)
那既然我們知道總和之後，就可以轉化問題為 "經過黑格子的走法有幾種?"
這時就可以假設終點也是黑格子，因為我們可以利用每一個黑格子之間的關係去求出從起點走到黑格子的方案數
然後我們就可以開始定義我們的 \(dp[i]\) 為，當走到第 \(i\) 個黑格子且不經過其他黑格子時可以有多少種走法。
然後你就會發現
\(dp[i]=C_{x_i-1}^{x_i-1+y_1-1} - \sum_{j=0}^{i-1} dp[j]\cdot C_{x_i-x_j}^{x_i-x_j+y_i-y_j}\)
然後我們只需要假設終點也是黑格子，求出到終點且不經過其他黑格子的方案數即可
於是就可以很輕鬆的算出作業的答案，那還有一個很大的問題，也就是我們要怎麼求出 \(C_y^x\) 呢?
組合論 
哈哈是我啦 沒錯我們就是要使用組合論
以下是組合數的板子(qpow 要自己寫)，那套這個板子就可以過剛剛那一題了。
ll fac[1'000'020],inv[1'000'020];
ll getInv(ll a){ return qpow(a,mod-2); } //逆元
void init(int n){ // O(N)
fac[0] = 1;
for(ll i = 1; i <= n; i++)
fac[i] = fac[i-1] * i % mod;
inv[n] = getInv(fac[n]);
for(ll i = n-1; i >= 0; i--)
inv[i] = inv[i+1] * (i+1) % mod;
}
ll C(int n,int m){ //O(1)
if(m > n) return 0;
return fac[n] * inv[m] % mod * inv[n-m] % mod;
}
複雜度 \(O(N)\) 預處理， \(O(1)\) 詢問
排列
定義 : 從 \(n\) 個不同元素中，任取 \(m\) 個元素按照一定的順序排成一列，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的一個排列；從 \(n\) 個不同元素中取出 \(m(m\leq n)\) 個元素的所有排列的個數，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的排列數，用符號 \(\mathrm A_m^n\)（或者是 \(\mathrm P_m^n\)）表示。
排列的計算公式為:
\(\mathrm A_m^n=n(n-1)(n-2)....(n-m+1)= \dfrac{n!}{(n-m)!}\)
而其中當 \(n==m\) 時，則是排列的特殊情況，也稱為 "全排列" 此時 \(\mathrm A_m^n\) 的答案為 \(n!\)
組合
定義 : 從 \(n\) 個不同元素中，任取 \(m\) 個元素組成一個集合，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的一個組合；從 \(n\) 個不同元素中取出 \(m\) 個元素的所有組合的個數，叫做從 \(n\) 個不同元素中取出 \(m\) 個元素的組合數。用符號 \(\mathrm C_m^n\) 來表示。
\(\mathrm C_m^n= \dfrac{\mathrm A_m^n}{m!}= \dfrac{n!}{m!(n-m)!}\)
二項式定理 (帕斯卡三角形)
這也是大家都上過的課程，其中
\((a+b)^n=\sum_{i=0}^{n} \mathrm C_i^n \cdot a^{n-i}b^i\)
而證明則可以使用數學歸納法證明。
如果可以在賽中解出這題，就代表你的二項式定理超強。(還有python)
題目敘述 : 給出一個數 \(x\) ，要求將其表示為不超過 \(5\) 個數的立方和的形式， \(x\) 範圍為 \(10^{100000}\)
首先，會知道第一件事情，對於任何數字 \(y\) ， \(y - (y\%6)^3\) 之後， \(y\) 必定為6的倍數。
1 - 1^3 = 0%6 == 0
2 - 2^3 = -6%6 == 0
3 - 3^3 = -24%6 == 0
4 - 4^3 = -60%6 == 0
5 - 5^3 = -120%6 == 0
所以第一個數字就是 \((x\%6)\) 那這樣剩下的 \(x-(x\%6)^3\) 就會是 \(6\) 的倍數
(PS: 不過我不認為這題是二項式)
然後通過二項式定理我們可以輕易地發現(湊出) :
\((a-1)^3+(a+1)^3+(-a)^3+(-a)^3=6a\)
接著我們把 \(a=x-(x\%6)^3\) 代進去(記得除\(6\))，所以答案剩餘的四個數字會是
\(\dfrac{x-(x\%6)^3}{6}+1 , \dfrac{x-(x\%6)^3}{6}-1, -\dfrac{x-(x\%6)^3}{6}, -\dfrac{x-(x\%6)^3}{6}\)
於是就可以得出答案為
\((x\%6), \dfrac{x-(x\%6)^3}{6}+1 , \dfrac{x-(x\%6)^3}{6}-1, -\dfrac{x-(x\%6)^3}{6}, -\dfrac{x-(x\%6)^3}{6}\)
因為範圍是 \(10^{100000}\) 所以你算完這些之後需要使用 PYTHON or JAVA 求解，或是手刻大數運算。
機率 DP
機率 DP 用於解決概率問題與期望問題，通常，解決機率問題需要順序循環，而解決期望問題使用逆序循環，如果定義的狀態轉移方程存在後效性問題，還需要用到高斯消元來優化。機率 DP 也會結合其他知識進行考察，例如 狀態壓縮，樹上進行 DP 轉移等。
不過今天只教最簡單的 入門版機率 DP
這類題目用順推，也就是從初始狀態推向結果。和一般的 DP 非常類似，難點依然是對狀態轉移方程的定義，只是這類題目經過了機率論知識的包裝。
簡單例題 骰子
題目敘述 : 骰子。骰 \(k\) 次，詢問總和在 \(a\sim b\) 之間的機率是多少。
我們可以立即的給定一個 \(dp[i]\) 為總和為 \(i\) 的機率是多少。
首先很簡單會發現骰 \(1\) 次，對於 1~6 他們的機率分別都是 \(\frac 1 6\)
所以我們的初始化就會是
double dp[N+1][6*N+1];
for(int i=1;i<=6;i++){
dp[1][i]=1.0/6.0;
}
然後我們只需要從第二次骰骰子開始做 dp 即可，每一次是加上可以從上一次轉移到自己的總和機率(也就是 1~6)
然後因為加了 6 個所以需要 /6
核心代碼
for(int k=1;k<=6;k++){
dp[i][j] += dp[i-1][j-k];
}
dp[i][j]/=6;
例題2 抓老鼠
題目大意：袋子裡有 \(w\) 隻白鼠和 \(b\) 隻黑鼠，公主和龍輪流從袋子裡抓老鼠。誰先抓到白色老鼠誰就贏，如果袋子裡沒有老鼠了並且沒有人抓到白色老鼠，那麽算龍贏。公主每次抓一隻老鼠，龍每次抓完一隻老鼠之後會有一隻老鼠跑出來。每次抓的老鼠和跑出來的老鼠都是隨機的。公主先抓。問公主贏的機率。
根據一些經驗，我們可以先定義 \(dp[i][j]\) 為，當有 \(i\) 隻白鼠和 \(j\) 隻黑鼠時公主贏的機率。
然後思考一下每一輪會有以下四種情況 :
-
公主抓到一隻白鼠，公主贏了。
機率為 \(\frac{i}{i+j}\) -
公主抓到一隻黑鼠，龍抓到一隻白鼠，龍贏了。
機率為 \(\frac{j}{i+j}\cdot \frac{i}{i+j-1}\) -
公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻黑鼠，轉移到 \(dp[i][j-3]\)。
機率為 \(\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}\) -
公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻白鼠，轉移到 \(dp[i-1][j-2]\)。
機率為 \(\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}\)
那由於我們是要問公主贏的機率，所以不需要計算第二種狀況，且需要保證第三，第四種狀況的可能性
#define ld long double
for (int i = 1; i <= w; i++) dp[i][0] = 1; // 初始化
for (int i = 1; i <= b; i++) dp[0][i] = 0;
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= b; j++) {
dp[i][j]+=(ld)i/(i+j);
if (j >= 3){
dp[i][j] += (ld)j/(i+j) * (ld)(j-1)/(i+j-1) * (ld)(j-2)/(i+j-2) * dp[i][j-3];
}
if (i >= 1 && j >= 2) {
dp[i][j] += (ld)j/(i+j) * (ld)(j-1)/(i+j-1) * (ld)i/(i+j-2) * dp[i-1][j-2];
}
}
}