前言

本文將介紹決策單調性優化 DP 的相關內容。持續更新修正，如有差錯請指出。

1.四邊形不等式優化 DP

1.1 四邊形不等式與決策單調性

• 四邊形不等式：如果對于任意的 \(a \le b \le c \le d\) 均成立

則稱代價函數 \(w\) 滿足四邊形不等式。觀察上述形式，即包含劣于相交，注意這是當我們要求代價函數 \(w\) 最小時四邊形不等式的符號，如果我們要求 \(w\) 最大，相當于對其取相反數，那么相應的，此時的四邊形不等式需要變號。
四邊形不等式優化利用的是狀態轉移方程中的決策單調性，通常用于解決一系列的最優化問題。
在解決動態規劃相關問題的時候，通常會遇到以下這種形式

其中 \(\min\) 也可能是 \(\max\)。一般情形下，這類問題解決的時間復雜度為 \(\mathcal{O(n^2)}\)，如果 \(f\) 具有決策單調性，那么就可以將時間復雜度優化至 \(\mathcal{O(n\log n)}\) 甚至 \(\mathcal{O(n)}\)。

• 決策單調性：設 \(p_i\) 表示 \(f_i\) 取到最小值時 \(j\) 的值（如果有多個 \(j\) 滿足則取最小），即 \(f_i\) 的最優決策點。當代價函數 \(w\) 滿足四邊形不等式時，\(p_i\) 在 \([1,n]\) 上單調不降，\(f\) 具有決策單調性。則我們有

要證明這一點，可以使用反證法。假設對于 \(f_i,f_j(i < j)\)，其最優決策點 \(p_j < p_i\)，此時 \(p_j < p_i < i < j\)，據四邊形不等式有 $$w(p_j,j) + w(p_i,i) \ge w(p_j,i) + w(p_i,j)$$但是根據決策點的最優化條件又有 \(w(p_i,i) \le w(p_j,i),w(p_j,j) \le w(p_i,i)\)，即 $$w(p_j,j) + w(p_i,i) \le w(p_j,i) + w(p_i,j)$$與四邊形不等式矛盾。
由此得證。

對于 \(f_i\)，其具有最小/最大最優決策點，將上述對 \(p_i\) 的定義更換為取最大后，關于原 \(p_i\) 的所有結論都是同樣成立的，最大最優決策點同樣具有單調不降的性質。注意可能存在 \(i < i'\)，但是 \(i'\) 的最大最優決策點小于 \(i'\) 的最小最優決策點，故一般題目當中我們都默認只取最小（大）最優決策點來轉移。

1.2 解題套路

通常我們先寫出 \(f_i\) 的轉移式子，大多數情況下，通常使用

來檢驗代價函數是否滿足四邊形不等式。

然后對于一個決策，取它作為最優決策點的 \(f_i\) 所組成的是一個區間。對于決策 \(p_i < p_{i'}\)，則這兩種決策能成為最優決策的區間 \([l_{p_i},r_{p_i}],[l_{p_{i'}},r_{p_{i'}}]\)，有 \(r_{p_i} < l_{p_{i'}}\)。

我們寫一個二分函數 \(check(j,i)\) 計算出第一個以 \(j\) 作為最優決策不如以 \(i\) 作為最優決策優秀的點，那么可以使用單調隊列來維護最優決策點，并進行 DP 轉移了。

2.斜率優化 DP

給出例題。

• P3195 玩具裝箱

對于 \([l,r]\) ，其代價為 \((r - l + \sum_{i = l}^r c_i - L)^2\)。

首先對 \(c_i\) 做前綴和。考慮暴力，對于每個 \(i\) 去枚舉 \(j\)，則有

rep(i,1,n) {
    dp[i] = inff;
    rep1(j,i - 1,0)
        chmin(dp[i],dp[j] + (i - j - 1 + c[i] - c[j] - L) * (i - j - 1 + c[i] - c[j] - L));
}

現在進行優化，把上述式子變形，把 \(1\) 放入 \(L\) 中，\(i,j\) 分別放入 \(c_i,c_j\) 中，有 \((c_i - c_j - L)^2\)，把式子里的“常量”提出來展開，變為

接下來考慮進行斜率優化，對于一個一次函數 \(y = kx + b\)，通常推式子時有以下操作：

1. 把要求最小值的式子作為截距，即 \(b = dp_i - (c_i - L)^2\)
2. 把另一邊的式子變為 \(y - kx\) 的形式，其中 \(y\) 只與 \(j\) 有關，\(kx\) 同時與 \(i,j\) 有關

顯然，\(b_i\) 取到最小值的點在這個下凸殼上，因為這個斜率是單調的，可以考慮用單調隊列來維護，此時 \(\text{slope}(q_{i - 1},q_i) < \text{slope}(q_{i},q_{i +1})\)。

那么當 \(\text{slope}(q_{i - 1},q_i) \leq k < \text{slope}(q_i,q_{i + 1})\)，\(b\) 在 \(q_i\) 上取得最小值。

代碼就很好寫了。

il db slope(int i,int j) {
    return (db)(y[i] - y[j]) * 1.0 / (db)(x[i] - x[j]);
}

il void solve() {
    //------------code------------
    read(n,L); 
    ++ L;
    rep(i,1,n) read(c[i]),c[i] += c[i - 1];
    rep(i,1,n) c[i] += i;
    rep(i,1,n) {
        int k = 2ll * (c[i] - L);
        while (hh <= tt && slope(q[hh - 1],q[hh]) <= k * 1.0) ++ hh;
        dp[i] = y[q[hh - 1]] - k * x[q[hh - 1]] + (c[i] - L) * (c[i] - L);
        x[i] = c[i],y[i] = dp[i] + c[i] * c[i];
        while (hh <= tt && slope(q[tt - 1],q[tt]) >= slope(q[tt],i)) -- tt;
        q[++ tt] = i;
    }
    write(dp[n],'\n');
    return ;
}