dp是一個在noip必考的項目（據(jù)說今年又要出新算法了），于是在機房老師的引導(dǎo)下，學習了斜率優(yōu)化dp（真是一個好東西）

下面說一下我的心得吧：

? 首先對于斜率優(yōu)化呢

? 這是一種無法用直接單調(diào)隊列優(yōu)化的算法，由于它的轉(zhuǎn)移方程中存在著一個或多個會根據(jù)當前狀態(tài)有關(guān)的量，故單調(diào)隊列無法直接優(yōu)化，而這里就用到了斜率優(yōu)化。

? 下面給出一道例題

P3195 [HNOI2008]玩具裝箱TOY

題目描述

P教授要去看奧運，但是他舍不下他的玩具，于是他決定把所有的玩具運到北京。他使用自己的壓縮器進行壓縮，其可以將任意物品變成一堆，再放到一種特殊的一維容器中。P教授有編號為?1\cdots N1?N?的?NN?件玩具，第?ii?件玩具經(jīng)過壓縮后變成一維長度為?C_iCi??.為了方便整理，P教授要求在一個一維容器中的玩具編號是連續(xù)的。同時如果一個一維容器中有多個玩具，那么兩件玩具之間要加入一個單位長度的填充物，形式地說如果將第?ii?件玩具到第?jj?個玩具放到一個容器中，那么容器的長度將為?x=j-i+\sum\limits_{k=i}^{j}C_kx=j?i+k=i∑j?Ck??制作容器的費用與容器的長度有關(guān)，根據(jù)教授研究，如果容器長度為?xx?,其制作費用為?(X-L)^2(X?L)2?.其中?LL?是一個常量。P教授不關(guān)心容器的數(shù)目，他可以制作出任意長度的容器，甚至超過?LL?。但他希望費用最小.

感謝@ACの666 提供的Latex題面

輸入輸出格式

輸入格式：

?

第一行輸入兩個整數(shù)N，L.接下來N行輸入Ci.1<=N<=50000,1<=L,Ci<=10^7

?

輸出格式：

?

輸出最小費用

?

輸入輸出樣例

輸入樣例#1：?復(fù)制

5 4 3 4 2 1 4

輸出樣例#1：?復(fù)制

1

我們發(fā)現(xiàn)這題的dp方程十分的簡單

? f[i]=min{f[j]+(sum[i]-sum[j]+i-j-l-1)^2}(看不懂或推不出的請學好dp再來）

方便起見 我們定義xa[i]=sum[i]+i? xb[i]:=sum[i]+i+l+1

轉(zhuǎn)移方程變?yōu)榱薴[i]=min{f[j]+(xa[i]-xb[j])^2}(0<=j<i)

?數(shù)據(jù)范圍一看就不是O（n^2）能承受的，我們必然要對其中的一維狀態(tài)或是一維轉(zhuǎn)移優(yōu)化

若是優(yōu)化狀態(tài)。。。。（O(1)的狀態(tài)那不就變貪心了嗎？？？，某些題的貪心性質(zhì)就是這樣被發(fā)現(xiàn)的）

但是這題我們沒有發(fā)現(xiàn)可以貪心的線索，那我們只能優(yōu)化轉(zhuǎn)移了

這里我們發(fā)現(xiàn)對于一個新的i的轉(zhuǎn)移有一個sum[i]和它-l的平方影響?，很明顯無法簡單使用單調(diào)隊列優(yōu)化轉(zhuǎn)移
在這里，我們不妨假設(shè)有j<k，對于i的轉(zhuǎn)移k比j優(yōu)

則就會得到

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f[j]+(xa[i]-xb[j])^2>f[k]+(xa[i]-xb[k])^2

打開這個式子：? ? ? ? ?f[j]+xa[i]^2+xb[j]^2-2*xa[i]*xb[j]>f[k]+xa[i]^2+xb[k]^2-2*xa[i]*xb[k]

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? f[j]+xb[j]^2-(f[k]+xb[k]^2)<2*xa[[i]*(xb[j]-xb[k])

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?這里就會很容易發(fā)生一些錯誤

由于j<k，那么這題的sum數(shù)組又是單調(diào)遞增的，則xb[j]-xb[k]其實是一個負數(shù)，當我們把他除過去的時候，不等號就會改變方向

我們發(fā)現(xiàn)? ? ??（f[j]+xb[j]^2-(f[k]+xb[k]^2)）/（2*(xb[j]-xb[k])）>xa[i]

?左邊只剩下了關(guān)于j和k的量，不妨用g（j，k）表示（f[j]+xb[j]^2-(f[k]+xb[k]^2)）/（2*(xb[j]-xb[k])）

于是我們發(fā)現(xiàn)當g（j，k）<xa[i]時k就會更優(yōu)

反之g（j,k）>xa[i]時j就會更優(yōu)，神奇的事情發(fā)生了

我們發(fā)現(xiàn)如果存在j1<j2<j3,g(j1,j2)>g(j2,j3）時無論xa[i]如何取值，在這里j2這個轉(zhuǎn)移一定不會是最優(yōu)的

那我們只要維護一個G單調(diào)不降就可以了

同時發(fā)現(xiàn)若xa[i]大于了單調(diào)隊列中最小的一個，后面的元素都會沒有用，所以在隊首維護一個單調(diào)性把小于xa[i]的值都彈出，每次取隊首的元素作為最優(yōu)的轉(zhuǎn)移對象，那么時間復(fù)雜度就會降到O（n）的時間范圍，一個元素只會進隊一次出隊一次，均攤O(1)

那么為什么要叫斜率優(yōu)化呢，我們發(fā)現(xiàn)g(j,k)里可以抽象的把j和k看做兩個點而g(j,k)可以看做是j到k的斜率，維護g的單調(diào)性就相當與維護一個二維的凸包，每次出現(xiàn)xa[i]，就是相當與用一條斜率為xa[i]的線去在這個凸包上截取最近的一個點。

那么斜率優(yōu)化也就講到這里了

安利一波代碼

var
n,l,i,j,head,tail:longint;
a,sum,xb,xa,f,q:array[0..1000000] of int64;
function g(a,b:longint):double;
begin
? exit((f[a]-f[b]+xb[a]*xb[a]-xb[b]*xb[b])/((xb[a]-xb[b])<<1));
end;
begin
? readln(n,l);
? for i:=1 to n do
? begin
? ? read(a[i]);
? ? sum[i]:=sum[i-1]+a[i];
? ? xa[i]:=sum[i]+i;
? ? xb[i]:=sum[i]+i+l+1;
? end;
? xb[0]:=l+1;
? head:=1; tail:=1;
? q[1]:=0;
? for i:=1 to n do
? begin
? ? while (head<tail) and (g(q[head+1],q[head])<xa[i]) do inc(head);
? ? j:=q[head];
? ? f[i]:=f[j]+(xa[i]-xb[j])*(xa[i]-xb[j]);
? ? while (head<tail) and (g(q[tail],q[tail-1])>g(q[tail-1],i)) do dec(tail);
? ? inc(tail); q[tail]:=i;
? end;
? writeln(f[n]);
end.

?

總結(jié)

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

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