說道斜率優(yōu)化，我就想起今年下半年 湖南2008年的一個(gè)題。相信大家也不陌生（如果您是第一次學(xué)斜率優(yōu)化，那估計(jì)挺陌生的）。題目叫：HNOI2008 玩具裝箱TOY。題意大概是這個(gè)樣子：

題意簡(jiǎn)述

給你一個(gè)序列$a_{[1,n]}$和一個(gè)常數(shù)$k$。請(qǐng)你把這個(gè)序列分成若干段。定義：一個(gè)段$[l,r]$需要占用的空間$X$就等于$r?l+\sum _{i=l}^r{a}_i$，然后需要的花費(fèi)就是$(X?k{)}^2$。其中這個(gè)$X$沒有限制，珂以無限長(zhǎng)（只不過不是最優(yōu)就是了）。請(qǐng)求出所有段的花費(fèi)的最小值。

暴力思路

如果您來看斜率優(yōu)化的話，相信您也不難退出這個(gè)題的暴力$dp$。設(shè)$dp[i]$表示前$i$個(gè)數(shù)分成一些段使得總花費(fèi)最小。那么，$dp[i]=mindp[j]+cost(j+1,i)$。其中$cost(j+1,i)$表示從$j+1$到$i$這些數(shù)在一段的花費(fèi)。為了稍微快一點(diǎn)，設(shè)$sum$表示$a$的前綴和。那么$cost(j+1,i)$就等于$[(i?j?1+sum[i]?sum[j])?l{]}^2$。

但是這個(gè)$dp$是$O(n^2)$的。能不能再快一點(diǎn)呢？（嚴(yán)格來講，你必須要再快一點(diǎn)，要不然這個(gè)時(shí)間就卡不過去）

正片開始：斜率優(yōu)化

把關(guān)于$i$的項(xiàng)和關(guān)于$j$的項(xiàng)單獨(dú)提出來。變成：

設(shè)$a(x)=x+sum[x],b(x)=x+sum[x]+l+1$。那么原式等于$(a(i)?b(j){)}^2$。

稍稍改變$j$的定義，令$j$是滿足條件中最優(yōu)的$j$。

那么：（推式子警告）

$$\begin{gathered} dp[i]=dp[j]+(a(i)?b(j){)}^2 \\ dp[i]=dp[j]+a(i{)}^2?2a(i)b(j)+b(j{)}^2 \\ dp[i]+2a(i)b(j)?a(i{)}^2=dp[j]+b(j{)}^2 \end{gathered}$$

把這個(gè)式子放到平面直角坐標(biāo)系上，以$b(j)$為$x$，$dp[j]+b(j{)}^2$為$y$。

對(duì)于每個(gè)$j$來說，點(diǎn)$(b(j),dp[j]+b(j{)}^2)$就是一個(gè)決策點(diǎn)了。

而且，顯然這是一個(gè)直線的關(guān)系，它的斜率就是$2a(i)$，截距是$dp[i]?a(i{)}^2$。我們把直線向上平移$a(i{)}^2$，就是最小的$dp[i]$。由于$a(i{)}^2$的值是確定的（我們?cè)谡?span id="ze8trgl8bvbq" class="katex--inline">$j$的過程中，$i$是不會(huì)變的），所以在同一個(gè)$i$里面，我們相當(dāng)于要讓截距最小。

這樣，對(duì)于每個(gè)$i$（注意，和上面不一樣，不在同一個(gè)$i$里面了），珂能作為最優(yōu)點(diǎn)選擇出來的點(diǎn)應(yīng)該組成一個(gè)下凸包（因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$a(i)$是單調(diào)遞增的，所以斜率單調(diào)遞增，即組成下凸包）。

（$a(i)$的單調(diào)遞增性我就不講了）

為啥？考慮這種情況：

（$A$，$B$，$C$是珂供選擇的三個(gè)決策點(diǎn)）

當(dāng)前的話，如果$A$還沒滾蛋，應(yīng)該是$A$比$B$優(yōu)的。如圖

隨著斜率的增加，也許會(huì)出現(xiàn)$C$比$A$和$B$都優(yōu)的情況。如圖：

容易證明，$C$此時(shí)一枝獨(dú)秀，$A$和$B$都珂以滾蛋了。這兩種情況有一個(gè)共同點(diǎn)，就是$B$都不能再優(yōu)了。anyway，滾蛋吧。

還有一種情況（肯定還有，只有剛剛那一個(gè)是沒法保證正確性的），就是最前面兩個(gè)元素還要滿足一個(gè)條件：第一個(gè)點(diǎn)和第二個(gè)點(diǎn)之間的斜率要$>=2a(i)$，否則第一個(gè)就再也不珂能作為最優(yōu)解出現(xiàn)了，因?yàn)榇藭r(shí)隨著斜率的單調(diào)遞增，后面的斜率肯定會(huì)更大，在當(dāng)下的$2a(i)$的斜率中第二個(gè)都比第一個(gè)優(yōu)，后面的話就不知道優(yōu)到哪里去了。所以第一個(gè)就再起不能，滾了。

如圖：

還是剛剛那張圖，不過是另一種滾蛋方法。此時(shí)紅色直線的斜率=$2a(i)$=$20$。當(dāng)紅色直線斜率為$20$的時(shí)候，$A$就沒有$B$優(yōu)了。如果再高一點(diǎn)，顯然，還是沒有$B$優(yōu)。所以以后這個(gè)$A$都不珂能比$B$更優(yōu)了。$A$就珂以滾蛋了。

說道這里，我們發(fā)現(xiàn)，這個(gè)東西珂以用一個(gè)單調(diào)隊(duì)列維護(hù)。維護(hù)完一個(gè)正確的隊(duì)列之后，$Q[head]$就是最優(yōu)解。

設(shè)隊(duì)列為$Q$，首尾分別叫$head,tail$。

總結(jié)一下，就是要維護(hù)兩個(gè)關(guān)系：

代碼：

#include<bits/stdc++.h> using namespace std; namespace Flandre_Scarlet {#define N 112345#define int long long #define F(i,l,r) for(int i=l;i<=r;++i)#define D(i,r,l) for(int i=r;i>=l;--i)#define Fs(i,l,r,c) for(int i=l;i<=r;c)#define Ds(i,r,l,c) for(int i=r;i>=l;c)#define Tra(i,u) for(int i=G.Start(u);~i;i=G.Next(i))#define MEM(x,a) memset(x,a,sizeof(x))#define FK(x) MEM(x,0)int n,l;int c[N];void R1(int &x){x=0;char c=getchar();int f=1;while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();x=(f==1)?x:-x;}void Input(){R1(n),R1(l);F(i,1,n) R1(c[i]),c[i]+=c[i-1];}int Q[N];int dp[N];int a(int i){return c[i]+i;}int b(int i){return c[i]+i+l+1;}int x(int i){return b(i);}int y(int i){return dp[i]+b(i)*b(i);}int slope(int i,int j)//計(jì)算斜率{return (y(i)-y(j))/(x(i)-x(j));}void Soviet(){int head=1,tail=1;F(i,1,n){while(head<tail and slope(Q[head],Q[head+1])<2*a(i)) ++head;//垃圾決策點(diǎn)出隊(duì)列dp[i]=dp[Q[head]]+(a(i)-b(Q[head]))* (a(i)-b(Q[head]));//Q[head]就是最優(yōu)的決策點(diǎn)。while(head<tail and slope(i,Q[tail-1])<slope(Q[tail-1],Q[tail])) --tail;Q[++tail]=i;//把i加入隊(duì)列}printf("%lld\n",dp[n]);}void IsMyWife(){Input();Soviet();}#undef int //long long } int main() {Flandre_Scarlet::IsMyWife();getchar();getchar();return 0; }

還有一些答疑時(shí)間（根據(jù)作者自身出現(xiàn)的理解問題編寫，以后支持評(píng)論功能之后珂能會(huì)根據(jù)評(píng)論區(qū)中的問題編寫。）

Q：既然$Q[head]$是最優(yōu)的，為啥還要存著后面的點(diǎn)呢？
A：后面的點(diǎn)雖然現(xiàn)在不是最優(yōu)的，但是它們很有潛力，等以后斜率上去之后，也許$Q[head]$就滾蛋了，后面那些點(diǎn)就變成了最優(yōu)。注意上面，我們說的是珂能成為最優(yōu)的點(diǎn)，而不是現(xiàn)在最優(yōu)的點(diǎn)。要為未來著想。

總結(jié)

以上是生活随笔為你收集整理的斜率优化 笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。