有一類DP狀態(tài)方程，例如：

dp[i]=min{dp[j]?a[i]?d[j]}??0≤j<i,d[j]≤d[j+1],a[i]≤a[i+1]

它的特征是存在一個既有 i 又有 j 的項 a[i]?d[j] 。編程時，如果簡單地對 i 和 j 循環(huán)，復雜度是 O(n2) 的。通過斜率優(yōu)化（凸殼優(yōu)化），把時間復雜度優(yōu)化到 O(n)。

斜率優(yōu)化的核心技術(shù)是斜率（凸殼）模型和單調(diào)隊列。

一、把狀態(tài)方程變換為平面的斜率問題

方程對某個固定的 i，求 j 變化時 dp[i] 的最優(yōu)值，所以可以把關(guān)于 i 的部分看成固定值，把關(guān)于 j 的部分看成變量。把 min 去掉，方程轉(zhuǎn)化為：dp[j]=a[i]?d[j]+dp[i]

為方便觀察，令：y=dp[j]，x=d[j]，k=a[i]，b=dp[i]，方程變?yōu)椋?span style="text-indent: 2em;">y=kx+b

斜率優(yōu)化的數(shù)學模型，就是把狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)換為平面坐標系直線的形式：y=kx+b。其中：

（1）變量 x 、y 和j 有關(guān)，并且只有 y 中包含 dp[j] 。點 (x,y) 是題目中可能的決策。

（2）斜率 k 、截距 b 與 i 關(guān)，并且只有 b 中包含 dp[i] 。最小的 b 包含最小的 dp[i]，也就是狀態(tài)方程的解。

注意應(yīng)用斜率優(yōu)化的2個條件：x 和 k 是單調(diào)增加的，即 x 隨著 j 遞增而遞增，k 隨著 i 遞增而遞增。

二、求一個dp[i]

先考慮固定 i 的情況下求 dp[i] 。由于 i 是定值，那么斜率 k=a[i] 可以看成常數(shù)。當 j 在 0≤j<i 內(nèi)變化時，對某個，產(chǎn)生一個點，這個點在一條直線上，是截距。如圖1。

圖1 經(jīng)過點(x, y)的直線

對于 0≤j<i 中所有的 j ，把它們對應(yīng)的點都畫在平面上，這些點對應(yīng)的直線的斜率 k=a[i] 都相同，只有截距 b 不同。在所有這些點中，有一個點 v ′ 所在的直線有最小截距 b ′ ，算出 b ′ ，由于 b ′ 中包含 dp[i]，那么就算出了最優(yōu)的 dp[i]。如圖。

圖2 經(jīng)過最優(yōu)點v'的直線

如何找最優(yōu)點v′？利用“下凸殼”。

前面提到，x 是單調(diào)增加的，即 x 隨著 j 遞增而遞增。下圖中給出了4個點，它們的 x 坐標是遞增的。

圖3 用下凸殼找最優(yōu)點

圖3(1)中的1、2、3構(gòu)成了“下凸殼”，“下凸殼”的特征是線段12的斜率小于線段23的斜率。2、3、4構(gòu)成了“上凸殼”。經(jīng)過上凸殼中間點3的直線，其截距b肯定小于經(jīng)過2或4的有相同斜率的直線的截距，所以點3肯定不是最優(yōu)點，去掉它。

去掉“上凸殼”后，得到圖3(2)，留下的點都滿足“下凸殼”關(guān)系。最優(yōu)點就在“下凸殼”上。例如在圖3(3)中，用斜率為k kk的直線來切這些點，設(shè)線段12的斜率小于k ，24的斜率大于k ，那么點2就是“下凸殼”的最優(yōu)點。

以上操作用單調(diào)隊列編程很方便。

（1）進隊操作，在隊列內(nèi)維護一個“下凸殼”，即每2個連續(xù)點組成的直線，其斜率是單調(diào)上升的。新的點進隊列時，確保它能與隊列中的點一起仍然能夠組成“下凸殼”。例如隊列尾部的2個點是v1、v2，準備加入隊列的新的點是v3。比較v1、v2、v3，看線段v1v2和v2v3的斜率是否遞增，如果是，那么v1、v2、v3形成了“下凸殼”；如果斜率不遞增，說明v2不對，從隊尾彈走它；然后繼續(xù)比較隊列尾部的2個點和v3；重復以上操作，直到v3能進隊為止。經(jīng)過以上操作，隊列內(nèi)的點組成了一個大的“下凸殼”，每2個點組成的直線，斜率遞增，隊列保持為單調(diào)隊列。

（2）出隊列，找到最優(yōu)點。設(shè)隊頭的2個點是v1、v2，如果線段v1v2的斜率比k 小，說明v1不是最優(yōu)點，彈走它，繼續(xù)比較隊頭新的2個點，一直到斜率大于k 為止，此時隊頭的點就是最優(yōu)點v ′ 。

三、求所有的dp[i]

以上求得了一個 dp[i]，復雜度 O(n)。如果對所有的 i ，每一個都這樣求 p[i]，總復雜度仍然是 O(n2) 的，并沒有改變計算的復雜度。有優(yōu)化的方法嗎？

一個較小的i1，它對應(yīng)的點是 {v0,v1,...,vi1}；一個較大的 i2，對應(yīng)了更多的點 {v0,v1,...,vi1,...,vi2}，其中包含了 i1 的所有點。當尋找i1的最優(yōu)點時，需要檢查 {0,v1,...,vi1}；尋找 i2 的最優(yōu)點時，需要檢查 {v0,v1,...,vi1,...,vi2}。這里做了重復的檢查，并且這些重復是可以避免的。這就是能優(yōu)化的地方，仍然用“下凸殼”進行優(yōu)化。

（1）每一個 i 所對應(yīng)的斜率 ki=a[i] 是不同的，根據(jù)約束條件 a[i]≤a[i+1]，當 i 增大時，斜率遞增。

圖4 多個 i 對應(yīng)的直線

（2）前面已經(jīng)提到，對一個i1找它的最優(yōu)點的時候，可以去掉一些點，即那些斜率比ki1小的點。這些被去掉的點，在后面更大的i2時，由于斜率ki2也更大，肯定也要被去掉。

根據(jù)（1）和（2）的討論，優(yōu)化方法是：對所有的 i ，統(tǒng)一用一個單調(diào)隊列處理所有的點；被較小的 i1 去掉的點，被單調(diào)隊列彈走，后面更大的 i2 不再處理它們。

因為每個點只進入一次單調(diào)隊列，總復雜度 O(n)。

下面的代碼演示了以上操作。

//q[]是單調(diào)隊列，head指向隊首，tail指向隊尾，slope()計算2個點組成的直線的斜率
for(int i=1;i<=n;i++){
    while(head<tail && slope(q[head],q[head+1])<k) //隊頭的2個點斜率小于k
        head++; //不合格，從隊頭彈出
    int j = q[head]; //隊頭是最優(yōu)點
    dp[i] = ...; //計算dp[i]
    while(head<tail && slope(i,q[tail-1])<slope(q[tail-1],q[tail])) //進隊操作
        tail--; //彈走隊尾不合格的點
    q[++tail] = i; //新的點進隊列
}

為加深對上述代碼的理解，考慮一個特例：進入隊列的點都符合“下凸殼”特征，且這些點組成的直線的斜率大于所有的斜率 ki，那么結(jié)果是：隊頭不會被彈出，進隊的點也不會被彈出，隊頭被重復使用 n 次。

圖5 一個特例

四、例題

下面用一個例題給出典型代碼。

題目描述：打印一篇包含 N 個單詞的文章，第i個單詞的打印成本為 Ci。在一行中打印k個單詞的花費是 ，M 是一個常數(shù)。如何安排文章，才能最小化費用？

輸入：有很多測試用例。對于每個測試用例，第一行中都有兩個數(shù)字 N 和 M（0≤n≤500000，0≤M≤1000）。然后，在接下來的2到 N + 1 行中有 N 個數(shù)字。輸入用 EOF 終止。

輸出：一個數(shù)字，表示打印文章的最低費用。

樣例輸入：

5 5

5

9

5

7

5

樣例輸出：

230

題目的意思是：有 N 個數(shù)和一個常數(shù) M ，把這 N 個數(shù)分成若干部分，每一部分的計算值為這部分數(shù)的和的平方加上 M ，總計算值為各部分計算值之和，求最小的總計算值。由于 N 很大，O(N2) 的算法超時。

設(shè)dp[i]表示輸出前i 個單詞的最小費用，DP轉(zhuǎn)移方程：

dp[i]=min{dp[j]+(sum[i]?sum[j])2+M}?? 0<j<i

其中 sum[i] 表示前 i 個數(shù)字和。

下面把DP方程改寫為 y=kx+b 的形式。首先展開方程：dp[j]+sum[i]?sum[i]+sum[j]?sum[j]?2?sum[i]?sum[j]+M

移項得：dp[j]+sum[j]?sum[j]=2?sum[i]?sum[j]+dp[i]?sum[i]?sum[i]?M

對照 y=kx+b，有：y=dp[j]+sum[j]?sum[j]，y 只和 j 有關(guān)。

x=2?sum[j]，x 只和 j 有關(guān)，且隨著 j 遞增而遞增。

k=sum[i]，k 只和 j 有關(guān)，且隨著 i 遞增而遞增。

b=dp[i]?sum[i]?sum[i]?M，b 只和 i 有關(guān)，且包含 dp[i]。

下面給出代碼。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;

int dp[MAXN];
int q[MAXN]; //單調(diào)隊列
int sum[MAXN];

int X(int x){ return 2*sum[x]; }
int Y(int x){ return dp[x]+sum[x]*sum[x]; }
//double slope(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));} //除法不好，改成下面的乘法
int slope_up  (int a,int b) { return Y(a)-Y(b);} //斜率的分子部分
int slope_down(int a,int b) { return X(a)-X(b);} //斜率的分母部分

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++) scanf("%d",&sum[i]);
        sum[0] = dp[0] = 0;
        for(int i=1;i<=n;i++) sum[i]+=sum[i-1];

        int head=1,tail=1; //隊頭隊尾
        q[tail]=0;
        for(int i=1;i<=n;i++){
            while(head<tail &&
                  slope_up(q[head+1],q[head])<=sum[i]*slope_down(q[head+1],q[head]))
               head++; //斜率小于k，從隊頭彈走

            int j = q[head]; //隊頭是最優(yōu)點
            dp[i] = dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]); //計算dp[i]

            while(head<tail &&
                              slope_up(i,q[tail])*slope_down(q[tail],q[tail-1])
                           <= slope_up(q[tail],q[tail-1])*slope_down(i,q[tail]))
                tail--; //彈走隊尾不合格的點
            q[++tail] = i; //新的點進隊尾
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}