斜率優化dp 學習筆記

2019-11-08 02:38:29

字體：大中小

來源：轉載

供稿：網友

從一個問題開始真正理解斜率優化dp orz ISA

1 問題

Apio 2010 特別行動隊

1.1 題意簡述

給出一個序列x1,x2...xn $x_1,x_2...x_n$ ，將其劃分成若干個連續的區間，每一段區間[l,r] $[l,r]$ 的價值為ax2+bx+c $ax^2+bx+c$ ，其中x=∑i=lrxi $x=/sum/limits_{i=l}^r x_i$ 現在你需要最大化序列的價值

1.2 數據范圍

對于20% $20/%$ 的數據，n≤1000 $n/le 1000$ 對于100% $100/%$ 的數據，1≤n≤106 $1/le n/le 10^6$ ，?5≤a≤?1 $-5/le a/le -1$ ，|b|≤107 $|b|/le 10^7$ ，|c|≤107 $|c|/le 10^7$ ，1≤xi≤100 $1/le x_i/le 100$

1.3 討論

1.3.1 20pts

令f(i) $f(i)$ 表示將序列的前i個劃分若干段的最大價值，si $s_i$ 表示序列的前綴和直接根據題意，可以列出狀態轉移方程 f(i)=max{f(j)+a?(si?sj)2+b?(si?sj)+c}，1≤j<i $f(i)=max/{f(j)+a*(s_i-s_j)^2+b*(s_i-s_j)+c/}，1/le j<i$ 然后直接dp就可以了時間復雜度O(n2) $O(n^2)$

1.3.2 100pts

數據范圍只能允許一個O(n) $O(n)$ 級別的算法

將轉移方程進一步展開，能得到 f(i)=max{f(j)+as2i?2asisj+as2j+bsi?bsj+c}，1≤j<i $f(i)=max/{f(j)+as_i^2-2as_is_j+as_j^2+bs_i-bs_j+c/}，1/le j<i$ 將其順序調整，寫成下面的形式 f(i)=max{?2asjsi+f(j)+as2j?bsj+as2i+bsi+c}，1≤j<i $f(i)=max/{-2as_js_i+f(j)+as_j^2-bs_j+as_i^2+bs_i+c/}，1/le j<i$ 觀察這個式子

首先，最后三項，只和a,b,c $a,b,c$ 以及si $s_i$ 有關。換句話說，在求f(i) $f(i)$ 的值時，這三項是與j $j$ 的選取無關的，我們稱之為常數項 對于常數項，可以直接將其拿到max之外 f(i)=max{?2asjsi+f(j)+as2j?bsj}+as2i+bsi+c，1≤j<i $f(i)=max/{-2as_js_i+f(j)+as_j^2-bs_j/}+as_i^2+bs_i+c，1/le j<i$

然后再觀察前面4項，可以發現si $s_i$ 是與j $j$ 的選取無關的，只與si $s_i$ 的選取有關；而其余都只與j $j$ 的選取有關，而與i $i$ 的選取無關 si $s_i$ 有什么性質？ si $s_i$ 為正項序列的前綴和，顯然它一定是對于1...n $1...n$ 單調遞增的在求解f(i) $f(i)$ 的過程中，我們也一定是按照1...n $1...n$ 的順序求，也就是說，在求解f(i) $f(i)$ 的過程中si $s_i$ 單調遞增

我們考慮將前四項抽象成一條直線令y=kx+b $y=kx+b$ 其中k=?2asj $k=-2as_j$ ，b=as2j?bsj $b=as_j^2-bs_j$ 也就是說，對于每一個j(1≤j≤n) $j(1/le j/le n)$ ，都有一條確定的直線那么在求解f(i) $f(i)$ 的時候，對于之前的一個確定的j $j$ ，將si $s_i$ 帶入解析式就能求出這個j $j$ 所對應的函數值如果枚舉每一個j $j$ ，求出相應的函數值來更新f(i) $f(i)$ 的話，實際上就是O(n2) $O(n^2)$ dp的方法了但是我們現在不能枚舉，需要直接求出，也就是說，需要確定一條能取到最優值的直線

所以說，什么是斜率優化dp？對于每一個i(1≤i≤n) $i(1/le i/le n)$ ，將i $i$ 抽象成一條直線求f(i) $f(i)$ 時，求之前的所有直線在自變量為某一個數時的最優值根據直線的斜率和自變量的增減關系，維護出一個O(n) $O(n)$ 的算法明白了這個之后，就已經基本上明白了斜率優化的大體過程

1.4 題解

對于這道題來說由于?5≤a≤?1 $-5/le a/le -1$ ，可以得出k>0 $k>0$ ，即所有直線的斜率為正由于si $s_i$ 單增，求f(i) $f(i)$ 的過程中，順次加入直線，直線的斜率也始終單增維護一個斜率單增的單調雙端隊列，兩個指針l,r

每一次加入一條直線yi $y_i$ 之前，判斷隊首的兩條直線yl $y_l$ 和yl+1 $y_{l+1}$ 在si $s_i$ 處的函數值，如果yl≤yl+1 $y_l/le y_{l+1}$ ，說明直線yl $y_l$ 已不是最優值，并且以后也不可能成為最優值，將其出隊計算f(i) $f(i)$ ，此時最優的直線即為隊首的直線yl $y_l$ 加入直線yi $y_i$ ，如果yi $y_i$ 與yr?1 $y_{r-1}$ 已經將yr $y_r$ 完全覆蓋，那么將yr $y_r$ 彈出

舉個栗子這里寫圖片描述在求解f(3) $f(3)$ 的時候，需要查看f(1) $f(1)$ 和f(2) $f(2)$ 所表示的兩條直線在s3 $s_3$ 處的函數值，然后取最大如圖所示，顯然選y2 $y_2$ 比選y1 $y_1$ 要優由于si $s_i$ 單增，以后在求解f(4)、f(5)... $f(4)、f(5)...$ 的時候，這兩條直線在s4、s5... $s_4、s_5...$ 處的函數值y1 $y1$ 也不可能比y2 $y2$ 更優，所以y1 $y1$ 實際上就已經可以扔掉了

還有一種情況這里寫圖片描述可以發現，順次插入y1,y2,y3 $y_1,y_2,y_3$ 這三條直線，因為要取最大值，y2 $y_2$ 實際上已經被y1 $y_1$ 和y3 $y_3$ 完全覆蓋了，無論si $s_i$ 取何值，它都已經不可能成為最優的答案，這個時候y2 $y_2$ 也可以扔掉了 實際上就是維護了一個下凸殼啊

我剛開始不明白為什么完全覆蓋的要扔掉，不扔直接做不行么這里有一個反例這里寫圖片描述此時y1 $y_1$ 和y3 $y_3$ 已經將y2 $y_2$ 完全覆蓋，應該扔掉但是如果不扔掉的話，查詢此時在s4 $s_4$ 處的最優值顯然y1>y2 $y1>y2$ ，這個時候會默認y1 $y_1$ 即為最優值，不會將y1 $y_1$ 彈出而實際上y3 $y_3$ 才是真正的最優值所以判斷是否有兩條直線將另外一條覆蓋是完全必要的

如何判斷兩條直線已經被另一條直線覆蓋？知識儲備：初中數學如上圖，令y1=k1x+b1,y2=k2x+b2,y3=k3x+b3 $y_1=k_1x+b_1,y_2=k_2x+b_2,y_3=k_3x+b_3$ 則求y1 $y_1$ 與y3 $y_3$ 的交點橫縱坐標為 k1x+b1=k3x+b3 $k_1x+b_1=k_3x+b_3$ x=b3?b1k1?k3 $x={b_3-b_1/over k_1-k_3}$ y=k1b3?b1k1?k3+b1 $y={k_1{b_3-b_1/over k_1-k_3}+b_1}$ 然后求y2 $y_2$ 在x $x$ 處的函數值 y2=k2b3?b1k1?k3+b2 $y_2=k_2{b_3-b_1/over k_1-k_3}+b_2$ 若y2≤y $y2/le y$ 即k2b3?b1k1?k3+b2≤k1b3?b1k1?k3+b1 $k_2{b_3-b_1/over k_1-k_3}+b_2/le {k_1{b_3-b_1/over k_1-k_3}+b_1}$ b3?b1k1?k3≤b2?b1k1?k2 ${b_3-b_1/over k_1-k_3}/le {b_2-b_1/over k_1-k_2}$ (k1?k3)?(b2?b1)≤(k1?k2)?(b3?b1) $(k_1-k_3)*(b_2-b_1)/le (k_1-k_2)*(b_3-b_1)$ 那么直線y2 $y_2$ 已經被y1 $y_1$ 和y3 $y_3$ 完全覆蓋如果斜率為負或者斜率單減的話別搞錯了正負號就好

這就是整個斜率優化的過程

1.5 代碼

代碼簡潔清晰明了

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 1000005int n,l,r;LL a,b,c,x;int q[N];LL s[N],f[N];LL K(int j) {return -2*a*s[j];}LL B(int j) {return f[j]+a*s[j]*s[j]-b*s[j];}LL Y(int i,int j) {return K(j)*s[i]+B(j);}bool cover(int x1,int x2,int x3){ LL w1=(K(x1)-K(x3))*(B(x2)-B(x1)); LL w2=(K(x1)-K(x2))*(B(x3)-B(x1)); return w1<=w2;}int main(){ scanf("%d",&n); scanf("%lld%lld%lld",&a,&b,&c); for (int i=1;i<=n;++i) scanf("%lld",&x),s[i]=s[i-1]+x; l=r=0; for (int i=1;i<=n;++i) { while (l<r&&Y(i,q[l])<=Y(i,q[l+1])) ++l; f[i]=Y(i,q[l])+a*s[i]*s[i]+b*s[i]+c; while (l<r&&cover(i,q[r],q[r-1])) --r; q[++r]=i; } 2 斜率優化dp

2.1 常見形式

斜率優化dp的狀態轉移方程有一些比較特殊的性質：

求解最值每一個狀態能轉化成一條直線在求解某一個狀態時，因變量為求解的狀態值，自變量為與這個狀態相關的量自變量滿足單調性，斜率滿足單調性

2.2 基本方法

將狀態轉移方程化成能表示成直線的形式找出自變量、因變量、斜率、截距，討論自變量的單調性、斜率的正負及單調性維護單調雙端隊列，維護上凸/下凸殼

3 相關題目

題目難度盡量遞增 ps 原來寫的代碼都好丑

bzoj1597 土地購買 http://blog.csdn.net/clove_unique/article/details/51244336 bzoj3156 防御準備 http://blog.csdn.net/clove_unique/article/details/51250213 bzoj3437 小P的牧場 http://blog.csdn.net/clove_unique/article/details/51297305 bzoj1010 hnoi2008 玩具裝箱 http://blog.csdn.net/Clove_unique/article/details/51225398 bzoj3675 apio2014 序列分割 http://blog.csdn.net/clove_unique/article/details/51297313 bzoj1096 zjoi2007 倉庫建設 http://blog.csdn.net/clove_unique/article/details/51244357 bzoj4518 sdoi2016 征途 http://blog.csdn.net/clove_unique/article/details/51224588