1. 首頁 > 生活百科 > >

dp優化 | 各種dp優化方式例題精選

生活百科

前言本文選題都較為基?。鲇糜謖故居嘔絞?nbsp;， 如果是要找題單而不是看基礎概念 ， 請忽略本文 。
本文包含一些常見的dp優化（“√”表示下文會進行展示，沒“√”表示暫時還咕著）：前綴和優化（√）、單調隊列優化（√）、斜率優化（√）、四邊形不等式優化、數據結構優化……
由于寫本文主要是記錄蒟蒻的dp優化學習過程，所以可能很不完善 ， 也會有很多錯誤 (?)。推薦看巨佬的：【學習筆記】動態規劃—各種 DP 優化 - 辰星凌
1. 前綴和優化dp進行狀態轉移時，如果發現需加上前面的一類狀態，就可以選擇使用數組進行累計操作，以達到降維度的效果 。
1.1 P1521 求逆序對1.1.1 題目大意給出 \(n\) ， \(k\) ， 問 \(1..n\) 的排列中正好有 \(k\) 個逆序對的排列數 。
1.1.2 數據范圍\(1 \leq n \leq 100\) ， \(1 \leq k \leq n * (n - 1) / 2\) 。
1.1.3 做法設 \(f_{i, j}\) 表示 \(1..i\) 的全排列中有 \(j\) 個逆序對的排列數 。答案即為 \(f_{n, k}\) 。
考慮在 \(1..(i-1)\) 的排列中加入一個 \(i\) 所能貢獻的逆序對數量 。由于 \(i\) 是最大的 ， 故當它被排在第 \(j\) 個時 ， 相應的逆序對數量會增加 \(i - j\) 個 。
不難列出轉移式：\(f_{i, j}=\sum_{k = 0}^{min(j, i - 1)}f_{i - 1, j - k}\) 。
其中的 \(k\) 表示新增的逆序對數 。
同時初始化 \(f_{1, 0}=1\) 。
由于此題比較水 ， 所以不優化也能過 。
const int N = 110, mod = 10000;int n, k, f[N][N * N >> 1];int main() { n = read(), k = read(); f[1][0] = 1; for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = 0; k <= min(j, i - 1); k++)f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod; printf("%d\n", f[n][k]); return 0;}接下來開始優化 。
現在把上面轉移的式子改一下 ， 方便優化：
\(f_{i, j}=\sum_{k = max(0, j - (i - 1))}^jf_{i - 1, k}\) ， 相應的，代碼可以改成這樣：
for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = max(0, j - (i - 1)); k <= j; k++)f[i][j] = (f[i][j] + f[i - 1][k]) % mod;開數組 \(s_{i, j}=\sum_{k = 0}^jf_{i, k}\)，那么 \(s_{i, j}=s_{i, j - 1}+f_{i, j}\)。
相應的，轉移式變為 \(f_{i, j}=s_{i - 1,j}-s_{i - 1, j - (i - 1) - 1}\)，注意邊界問題 。
for (int i = 1; i <= n; i++) f[i][0] = s[i][0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[i - 1][j] = (s[i - 1][j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[i - 1][j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[i - 1][j - (i - 1) - 1])) % mod; }注意到 \(s\) 數組的前一維似乎沒有什么用處，考慮使用滾動數組繼續優化 。
for (int i = 1; i <= n; i++) f[i][0] = 1; s[0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; }1.2 P2513 [HAOI2009]逆序對數列1.2.1 題目大意給出 \(n\)，\(k\)，問 \(1..n\) 的排列中正好有 \(k\) 個逆序對的排列數 。
1.2.2 數據范圍\(1 \leq n, k \leq 1000\) 。
1.2.3 做法乍一眼看是不是和上題一模一樣 。
如果直接提交上題的代碼（改了數據范圍），就會得到30分的好成績 。（最后幾個點全部MLE）
稍稍計算一下，就會發現 \(499500000\) 的 int 數組是不是有那么億點點大？
那么如何優化代碼呢？
注意到上題的代碼中，逆序對數枚舉的上限為 \(\frac {n \times (n-1)} {2}\)，再瞅一眼本題數據范圍，最大逆序對數只有 \(1000\)？！
不難想到改成以下代碼：
const int N = 1010, mod = 10000;int n, k, f[N][N], s[N ];int main() { n = read(), k = read(); for (int i = 1; i <= n; i++) f[i][0] = 1; s[0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= min((i * (i - 1)) >> 1, k); j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= min((i * (i - 1)) >> 1, k); j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; } printf("%d\n", f[n][k]); return 0;}真好，既優化了空間又優化了時間 。
2. 單調隊列優化dpOI-Wiki 傳送門
借助單調隊列的單調性，及時排除不可能的決策 ， 保持候選集合的高度有效性和秩序性 。
單調隊列尤其適合優化決策取值范圍的上、下界均單調變化，每個決策在候選集合中插入或刪除至多一側的問題 。

推薦閱讀