動態(tài)規(guī)劃——決策單調性優(yōu)化DP 學習筆記

決策單調性

對于最優(yōu)性問題，常有狀態(tài)轉移方程：\(f_i = \min/\max\{f_j\dots\}\)，

形象的：如果 \(i\) 的最優(yōu)轉移點是 \(j\)，\(i'\) 的最優(yōu)轉移點是 \(j'\)，當 \(i<i'\) 時，有 \(j\le j'\)，則稱該 DP 問題具有決策單調性。

即：\(i\) 單增，其最優(yōu)轉移點單調不減。

如何發(fā)現(xiàn)一個轉移方程具有決策單調性？打表。

使用

一、離線決策單調性

形如：\(f(i, j) = \min\limits_{k \le j}\{f(i-1, k)+\text{cost}(k,j)\}\)，轉移分層.

形象的：\(f(i, j)\) 表示將前 \(j\) 個物品分為 \(i\) 端的最小花費，則原式意為，枚舉一個 \(k\) 個，將前 \(k\) 個分為 \(i-1\) 段，再加上后面這一段所需的花費。

那么此時，最 native 的算法是，三層循環(huán)枚舉，時間復雜度就是 \(O(nm^2)\) 的。

決策單調性：設 \(k\) 為 \(f(i,j)\) 的最優(yōu)轉移點，\(k'\) 為 \(f(i, j')\) 的最優(yōu)轉移點，當 \(j<j'\) 時有 \(k\le k'\)，則該 DP 具有決策單調性。

形象的：對于每一層（固定 \(i\) 不變），\(j\) 單增，其最優(yōu)轉移點（在 \(i-1\) 層上）單調不減。

因此，我們可以一層一層的 DP，對于第 \(i\) 層，我們先算 \(f(i, \mathrm{mid})\)，其中 \(\mathrm{mid} = m/2\)；同時求出 \(f(i, \mathrm{mid})\) 的最優(yōu)轉移點 \(f(i-1, \mathrm{opt})\)。那么 \([1,i-1]\) 的最優(yōu)轉移點只能在 \(f(i-1,1\dots \mathrm{opt})\) 中取，\([i+1,n]\) 的最優(yōu)轉移點只能在 \(f(i-1,\mathrm{opt}\dots n)\) 中取。

如圖：

遞歸下去，即：

\(s(i,l,r,p,q)\) 表示算 \(f(i,l\dots r)\) 且最優(yōu)轉移點只可能在 \(f(i-1,p\dots q)\)中，先算 \(f(i,\mathrm{mid})\) 的值（即枚舉 \(p\) 到 \(q\)），求出最優(yōu)轉移點 \(\mathrm{opt}\)。

然后遞歸求解：\(s(i,l,r,p,q)\rightarrow\left\{\begin{array}{c}s(i,l,\mathrm{mid}-1,p,\mathrm{opt})\\s(i,\mathrm{mid}+1,r,\mathrm{opt},q)\end{array}\right.\).

則時間復雜度為 \(O(nm \log m)\)。

例題：CF321E Ciel and Gondolas.

inline int cost(const int x, const int y) {
    return (s[y][y] - s[y][x - 1] - s[x - 1][y] + s[x - 1][x - 1]) >> 1;
} signed main() {
    int n = ur, k = ur;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) s[i][j] = ur + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    memset(f, 0x3f, sizeof f); for (int i = 0; i <= n; ++i) f[i][0] = 0;
    for (int i = 1; i <= k; ++i) for (int j = 0; j <= n; ++j) {
        for (int t = 0; t <= j; ++t) f[i][j] = min(f[i][j], f[i - 1][t] + cost(t + 1, j));
    } printf("%d\n", f[k][n]);
    return 0;
}

inline int cost(const int x, const int y) {
    return (s[y][y] - s[y][x - 1] - s[x - 1][y] + s[x - 1][x - 1]) >> 1;
} void solve(int i, int l, int r, int p, int q) {
    if (l > r) return;
    int j = l + r >> 1, opt = 0;
    for (int t = p; t <= q && t <= j; ++t) {
        int e = f[i - 1][t] + cost(t + 1, j);
        if (f[i][j] > e) f[i][j] = e, opt = t;
    }
    solve(i, l, j - 1, p, opt);
    solve(i, j + 1, r, opt, q);
} signed main() {
    int n = rr, k = rr;
    for (int i = 1; i <= n; ++i) for (int j = 1 ; j <= n; ++j) s[i][j] = rr + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    memset(f, 0x3f, sizeof f); f[0][0] = 0;
    for (int i = 1; i <= k; ++i) solve(i, 0, n, 0, n);
    printf("%d\n", f[k][n]);
    return 0;
}

二、離線決策單調性

一維 DP，形如：\(f_r=\min\limits_{l=1}^{r-1}\{f_l+\text{cost}(l,r)\}\).

其決策單調性為 \(i\) 單增，其最優(yōu)轉移點 \(j\) 單調不見，比如：11122222244 這種。

沒聽懂 zhq 老師講的，等著看 wzm 的回放。。。

三、區(qū)間 DP 決策單調性

對于最優(yōu)化的區(qū)間 DP，設 \(d_{i,j}\) 為 \(f_{i,j}\) 的最優(yōu)轉移點，具有決策單調性的條件為 \(d_{l,r-1} \le d_{l,r} \le d_{l+1,r}\)。

求解方法：按長度枚舉區(qū)間；計算 \(f_{lr}\) 的時候，從 \(d_{l,r-1}\) 枚舉到 \(d_{l+1,r}\)。

時間復雜度：\(O(n^2)\)，神奇的證明（\(\text{By zhq}\)）如圖：

題單

見：https://www.luogu.com.cn/training/386809

Reference

[1] https://oi-wiki.org/dp/opt/quadrangle/
[2] https://www.cnblogs.com/lnzwz/p/12444390.html
[3] https://www.cnblogs.com/lhm-/p/12229791.html
[4] https://www.luogu.com.cn/blog/command-block/dp-di-jue-ce-dan-diao-xing-you-hua-zong-jie文章來源地址http://www.zghlxwxcb.cn/news/detail-711388.html

到了這里，關于動態(tài)規(guī)劃——決策單調性優(yōu)化DP 學習筆記的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！