鏈接：https://share.weiyun.com/5LzbzAc

目錄

前言

斜率優(yōu)化前期準(zhǔn)備

1.從狀態(tài)轉(zhuǎn)移方程出發(fā)

2.推理狀態(tài)轉(zhuǎn)移方程

對(duì)結(jié)論的進(jìn)一步推導(dǎo)

干貨！綜合結(jié)論

?判斷斜率大小的方法：叉乘

正片開始：代碼部分

后記

---

---

---

前言

之前我們對(duì)DP優(yōu)化已經(jīng)有了很多的了解，比如：單調(diào)隊(duì)列優(yōu)化DP，四邊形優(yōu)化DP。

今天，我們要講的是傳說中的斜率優(yōu)化。它與四邊形優(yōu)化相似，都是從數(shù)學(xué)角度上來推理。斜率優(yōu)化在四邊形優(yōu)化上又需要更復(fù)雜的數(shù)學(xué)推理，其中涉及到的求一條直線的斜率，以及運(yùn)用叉乘來判斷兩條直線的斜率大小，都足以讓初學(xué)者望而生畏。但只要理解透了其中的數(shù)學(xué)方法，也就是那么回事，挺簡(jiǎn)單的（我們老師說能第一次理解的人很少，所以如果你看不懂得話，可以第二天再來看一遍）。我在理解斜率優(yōu)化時(shí)也是非常的煎熬，現(xiàn)在也是剛剛?cè)腴T，所以有些地方寫的有紕漏的話請(qǐng)見諒。

---

斜率優(yōu)化前期準(zhǔn)備

1.從狀態(tài)轉(zhuǎn)移方程出發(fā)

既然是一種優(yōu)化DP的方法，那么他的起點(diǎn)就一定離不開狀態(tài)轉(zhuǎn)移方程。所以讓我們來看一下這個(gè)轉(zhuǎn)移方程

這是一個(gè)很簡(jiǎn)單的狀態(tài)轉(zhuǎn)移方程，很容易想到用單調(diào)隊(duì)列優(yōu)化把時(shí)間復(fù)雜度降到。（如果你不知道單調(diào)隊(duì)列優(yōu)化DP，應(yīng)該看看，因?yàn)榻酉聛淼男甭蕛?yōu)化也要用到它）

How about this?(那么這個(gè)轉(zhuǎn)移方程呢？）

觀察這個(gè)轉(zhuǎn)移方程，現(xiàn)在它還能用單調(diào)隊(duì)列優(yōu)化嗎？顯然不能。拆開這一項(xiàng)，會(huì)得到,它不能分解為只與i或j有關(guān)的部分。于是上面的單調(diào)隊(duì)列優(yōu)化方法就不好使了，于是就引出了我們今天要學(xué)的內(nèi)容：斜率優(yōu)化了。

先來看看此題：Print Article

?題目大意：輸出N個(gè)數(shù)字a[N]，輸出的時(shí)候可以連續(xù)的輸出，每連續(xù)輸出一串，它的費(fèi)用是 “這串?dāng)?shù)字和的平方加上一個(gè)常數(shù)M”。n<=500000，求最下的費(fèi)用。

此題轉(zhuǎn)移方程就是(sum為前綴和也就是a1+a2+...+ai）

假設(shè)i是當(dāng)前循環(huán)最外層，也就是可以假設(shè)它是一個(gè)常量。在不優(yōu)化的情況下，我們是把j從1到i-1循環(huán)，找出最小決策點(diǎn)j來使最小。所以我們的主要任務(wù)就是找出最優(yōu)決策點(diǎn)j。下面讓我們來看看是怎么推出斜率優(yōu)化的。

2.推理狀態(tài)轉(zhuǎn)移方程

我們考慮兩個(gè)決策點(diǎn)k與j，如果決策j更優(yōu)，那么也就是,好了，現(xiàn)在只要用一下你們的紙和筆，就可以推出這個(gè)式子：

似乎只能化簡(jiǎn)這么多了。但讓我們觀察不等式的右邊這一項(xiàng)，因?yàn)槲覀円呀?jīng)規(guī)定了sum為前綴和數(shù)組；

所以如果j>k,則sum[j]-sum[k]是>0的，化簡(jiǎn)后得;

如果j<k,則sum[j]-sum[k]<0，得

觀察這個(gè)式子,我們可以把設(shè)為,設(shè)為(相當(dāng)于把x,y,看成兩個(gè)函數(shù)），則上式可以化簡(jiǎn)為：

如果有j>k,則sum[j]-sum[k]<0，有等價(jià)于決策j優(yōu)于k

如果有j<k,則sum[j]-sum[k]<0，有等價(jià)于決策j優(yōu)于k

（這里講的有點(diǎn)快，說一下，sum[i]已經(jīng)被設(shè)為常數(shù)了）

既然我們已經(jīng)把他們?cè)O(shè)為x,y了，則可以把這兩個(gè)式子代入平面直角坐標(biāo)系里（滑稽），那么j和k就是坐標(biāo)系上的兩個(gè)點(diǎn)，所以就是兩個(gè)坐標(biāo)的直線的斜率（如果你不懂什么是斜率，請(qǐng)看這里）。

那么我們就可以得出我們的第一個(gè)結(jié)論：如果兩個(gè)決策點(diǎn)的斜率小于sum[i],則靠后的決策點(diǎn)更優(yōu)；否則靠前的決策點(diǎn)更優(yōu)。——結(jié)論1.斜率則是程序中是用函數(shù)來實(shí)現(xiàn)的。

也就是說在我們碰到其他題時(shí)，也需要用類似的方法對(duì)狀態(tài)轉(zhuǎn)移方程進(jìn)行化簡(jiǎn)，并求出函數(shù)x和函數(shù)y.

---

對(duì)結(jié)論的進(jìn)一步推導(dǎo)

盡管我們已經(jīng)得出了一個(gè)逼格很高的結(jié)論，但這對(duì)于斜率優(yōu)化是遠(yuǎn)遠(yuǎn)不夠的，所以我們還要對(duì)此結(jié)論進(jìn)一步推導(dǎo)。

先設(shè)一個(gè)函數(shù)g(i,j)為點(diǎn)i和點(diǎn)j之間的斜率，也就是。然后，讓我們考慮3個(gè)決策點(diǎn)的情況:i,j,k，k<j<i且（也就是k到j(luò)的斜率大于i到j(luò)的斜率。為了方便理解，這里給出圖像）。

下面讓我們利用我們剛才得出的結(jié)論1，?升級(jí)我們的結(jié)論。

可以分三種情況來討論，設(shè)結(jié)論1里的sum[i]為一個(gè)常量P。

(當(dāng)我們?cè)诳紤]斜率大小時(shí)，我們可以這樣想：斜率越大，直線就越斜。上圖中的就比要斜）

這里貼出結(jié)論方便結(jié)合圖理解：如果兩個(gè)決策點(diǎn)的斜率小于P,則靠后的決策點(diǎn)更優(yōu)；否則靠前的決策點(diǎn)更優(yōu)。

?1.如果與均小于P，則j比i優(yōu)，k比j優(yōu)。所以最優(yōu)決策點(diǎn)為k

?2.如果與均大于P,則j比k優(yōu)，i比j優(yōu)。所以最優(yōu)決策點(diǎn)為i

?3.如果g[i][j]<P且g[j][k]>P，則i比j優(yōu)，k比j優(yōu)。所以最優(yōu)決策點(diǎn)不為j

根據(jù)對(duì)3個(gè)情況的推理，我們發(fā)現(xiàn)不論如何，j都無法成為最佳決策點(diǎn)，所以可以排除j。于是就得出了我們的第2個(gè)論斷：所有的決策點(diǎn)滿足一個(gè)下凸包性質(zhì)，也就是最優(yōu)決策點(diǎn)的斜率是單調(diào)遞增的。

下凸包就是如圖的情況：

這里我們就可以代入單調(diào)隊(duì)列了。為什么？因?yàn)橛缮鲜鑫覀兊玫降慕Y(jié)論，我們知道這些最優(yōu)決策點(diǎn)相鄰之間的斜率是單調(diào)遞增的。將這些決策點(diǎn)放入隊(duì)列，這個(gè)隊(duì)列就具有了單調(diào)性，也就是可以用單調(diào)隊(duì)列來實(shí)現(xiàn)了。

設(shè)這個(gè)單調(diào)隊(duì)列q里存的決策點(diǎn)a,b，a<b，當(dāng)前的數(shù)組sum[i]是會(huì)隨著i遞增的；當(dāng)我們的最優(yōu)決策點(diǎn)取在b時(shí),b前面的所有決策點(diǎn)都將無效！為什么？因?yàn)閟um[i]是遞增的，所以需要我們匹配的斜率也是越來越大的，因?yàn)閍<b，a前面的所有決策點(diǎn)都小于a，所以a及a前面的所有決策點(diǎn)都將無效。(在程序中，我們?cè)趩握{(diào)隊(duì)列之中的實(shí)現(xiàn)就是彈出隊(duì)頭。)但隨著i的增加，b也可能不再適用，于是可以拿b與b后一個(gè)點(diǎn)c的斜率與sum[i]作比較:如果<sum[i]，則彈出b。知道為止。

---

干貨！綜合結(jié)論

所以我們對(duì)程序的優(yōu)化應(yīng)該這樣來實(shí)現(xiàn)：

?1，用一個(gè)單調(diào)隊(duì)列來維護(hù)所有決策點(diǎn)。

?2，找最佳決策點(diǎn)時(shí)，設(shè)當(dāng)前求解狀態(tài)為i，從隊(duì)頭開始，如果已有元素a b c，當(dāng)i點(diǎn)要求解時(shí)，如果<sum[i]，那么說明b點(diǎn)比a點(diǎn)更優(yōu)，a點(diǎn)可以排除，于是a出隊(duì)，直到第一次遇到>sum[i]，此時(shí)j-1即為最佳決策點(diǎn)。

?3，假設(shè)隊(duì)列中從頭到尾已經(jīng)有元素a b c。那么當(dāng)d要入隊(duì)的時(shí)候，我們維護(hù)隊(duì)列的下凸性質(zhì)，即如果<，那么就將c點(diǎn)刪除。直到找到>=為止，并將d點(diǎn)加入在該位置中。

Ps:寫到這里有點(diǎn)寫不下去了，于是直接粘貼了老師課件的原話。所以結(jié)合一下待會(huì)兒的代碼湊合著看吧。。。。。。

---

?判斷斜率大小的方法：叉乘

(這個(gè)部分原來是沒有的，現(xiàn)在抽出空來補(bǔ)充一下）

因?yàn)樯衔纳婕暗脚袛嘈甭实拇笮?#xff0c;但通常我們判斷斜率是直接通過比較大小來比較的。雖然這種方法很方便，但因?yàn)樯婕暗匠ǖ木葐栴}，這里引入一個(gè)叉乘的概念。

要運(yùn)用叉乘來判斷斜率的大小，我們還要知道一個(gè)東西叫向量，通常用字母p來表示。

向量可以看成一條線段。在平面直角坐標(biāo)系中，如果有一條直線，它的一個(gè)端點(diǎn)坐標(biāo)為(x1,y1),另一個(gè)端點(diǎn)坐標(biāo)為(x2,y2)。

那么這條線段的線段就為p(x1-x2,y1-y2)。（相當(dāng)于把這條線段平移到了原點(diǎn)）

（記住，結(jié)論中我們也將那些決策點(diǎn)連成了線段）

設(shè)有二向量p1(x3,y3),p2(x4,y4)。

則它們的叉乘p1×p2=(x3*y4-x4*y3)。在物理上，它們可以表示為一個(gè)平行四邊形的有向面積。所以：

?若p1×p2>0，則p2在p1的逆時(shí)針方向；

?若p1×p2<0，則p2在p1的順時(shí)針方向；

?若p1×p2=0，則p1與p2方向重合。

所以我們可以就可以結(jié)合上面的結(jié)論的最后一條。因?yàn)槲覀円ＷC最后隊(duì)尾三個(gè)決策點(diǎn)為下凸包，所以我們?cè)趶年?duì)尾入隊(duì)時(shí)，先將向量求出來，再用叉乘判斷它們是否為下凸包。如果是，則退出循環(huán)；如果不是，則彈出隊(duì)尾。

---

正片開始：代碼部分

注釋已經(jīng)打好了，結(jié)合著上面的結(jié)論看吧.

#include <iostream> #include <cstdio> #include <cstring> #include <queue>using namespace std;#define infI 0x3f #define infL 1LL<<60 #define N 500010 #define LL long long #define mem(a,n) memset(a,n,sizeof(a));LL read() {LL f=1,s=0;char a=getchar();while(!(a>='0'&&a<='9')) { if(a=='-') f=-1 ; a=getchar(); }while(a>='0'&&a<='9') { s=s*10+a-'0'; a=getchar();}return f*s; }LL sum[N],f[N],q[N]; int head,tail=1,n,m;LL px(LL i) {//求一個(gè)點(diǎn)的橫坐標(biāo)xreturn sum[i]*2; }LL py(LL i) {//求一個(gè)點(diǎn)的縱坐標(biāo)yreturn sum[i]*sum[i]+f[i]; }int main() {while(cin>>n>>m) {//循環(huán)讀入mem(f,0);mem(q,0);head=0,tail=1;for(int i=1;i<=n;i++)//初始化sum數(shù)組sum[i]=read();for(int i=1;i<=n;i++)sum[i]+=sum[i-1];for(int i=1;i<=n;i++) {while( head+1<tail && (py(q[head+1])-py(q[head])) <= sum[i]*( px(q[head+1]) - px(q[head] ) ) )//實(shí)現(xiàn)總結(jié)論的第2條；(py(q[head+1])-py(q[head]))求的是斜率。//PS：你們可能看不懂，這里為了避免循環(huán)的精度問題進(jìn)行了移項(xiàng)。head++;f[i]=f[q[head]]+m+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]);//動(dòng)態(tài)規(guī)劃while( head+1 < tail && (px(q[tail-1])-px(q[tail-2]))*(py(i)-py(q[tail-1])) <= (px(i)-px(q[tail-1]))*(py(q[tail-1])-py(q[tail-2])))//判斷斜率大小，這里運(yùn)用了叉乘的方法。 tail--;q[tail++]=i;}cout<<f[n]<<endl;}}

?

后記

在寫博客的過程中，我自己也感覺到了對(duì)斜率優(yōu)化不是很了解，相當(dāng)于復(fù)習(xí)了一遍，還是很感慨的.

總結(jié)

以上是生活随笔為你收集整理的C++剑指offer:解题报告之DP优化学习记 （二） ——浅论DP斜率优化 （Print Article 【HDU - 3507】 ）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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