『玩具裝箱TOY 斜率優化DP』
玩具裝箱TOY(HNOI2008)
Description
P教授要去看奧運,但是他舍不下他的玩具,於是他決定把所有的玩具運到北京。他使用自己的壓縮器進行壓縮,其可以將任意物品變成一堆,再放到一種特殊的一維容器中。P教授有編號為 \(1. . .N\) 的 \(N\) 件玩具,第 \(i\) 件玩具經過壓縮後變成一維長度為 \(C_i\) .為了方便整理, \(P\) 教授要求在一個一維容器中的玩具編號是連續的。同時如果一個一維容器中有多個玩具,那麼兩件玩具之間要加入一個單位長度的填充物,形式地說如果將第 \(i\) 件玩具到第 \(j\) 個玩具放到一個容器中,那麼容器的長度將為 \(x=j-i+\sum_{k=i}^jC_k\) 製作容器的費用與容器的長度有關,根據教授研究,如果容器長度為 \(x\) ,其製作費用為 \((x-L)^2\) .其中 \(L\) 是一個常量。 \(P\) 教授不關心容器的數目,他可以製作出任意長度的容器,甚至超過 \(L\) 。但他希望費用最小.
Input Format
第一行輸入兩個整數 \(N\) , \(L\) .接下來N行輸入 \(C_i\) . \(1<=N<=50000,1<=L,C_i<=10^7\)
Output Format
輸出最小費用
Sample Input
Sample Output
解析
簡單分析題目大意:給定一個數列,可以將其分為若干個連續的子段,將區間 \([i,j]\) 分為一段的花費為 \((j-i+\sum_{k=i}^jC_k-L)^2\) ,求最小劃分總花費。
由於沒有需要劃分多少段的限制,可以直接簡單地設定狀態:f[i]代表完成了前i個數的劃分的最小花費和。
區間的花費是利用字首和可以O(1)求解的,那麼狀態轉移方程就是 \[f_i=min\{f_j+(i-(j+1)+sum_i-sum_j-L)^2\}\]
暴力思路: \(O(n^2)\) 列舉 \(i,j\) 求解。
但是 \(50000\) 的資料 \(O(n^2)\) 肯定不行啊,我們考慮優化這個dp。
先化簡括號內花費內容:
\[ (i-(j+1)+sum_i-sum_j-L)^2 \\=(i-j-1+sum_i-sum_j-L)^2 \\=((i+sum_i)+(-L-1-j-sum_j))^2 \\設a_k=(k+sum_k),b_k=(a_k+L+1) \\=(a_i-b_j)^2 \]
代回原式:
\[ f_i=min\{f_j+(a_i-b_j)^2\} \]
假設我們已經找到了最優的 \(f_j\) ,那麼:
\[ f_i=f_j+(a_i-b_j)^2 \\⇒f_i=f_j+a_i^2-2a_ib_j+b_j^2 \\⇒f_j+b_j^2=2a_ib_j+(f_i-a_i^2) \]
(將只與i有關的項和只與j有關的項分別整理)
這個時候我們發現式子中有一項是即和 \(i\) 有關有和 \(j\) 有關的,然後就可以做一些神奇的優化了。
我們視 \(f_j+b_j^2\) 為 \(y\) , \(b_j\) 為 \(x\) , \(2a_i\) 為 \(k\) , \((f_i+a_i^2)\) 為 \(b\),那麼我們就可以把它當做一個一次函式的的表示式
\(y=kx+b\)
。而且這個一次函式需滿足:
1.過定點 \((b_j,f_j+b_j^2)\) ,由於這個點只和 \(j\) 有關,稱其為 \(P_j\)
\(2a_i\)
這時候,我們需要重新定義 \(f_i\) 的含義: 滿足兩個要求的一次函式的截距 \((b)\) 加上 \(a_i^2\) 。
由於 \(a_i^2\) 的值是確定的,我們需要求最小的 \(f_i\) ,即求做小的一次函式的截距。
我們將滿足斜率為 \(2a_i\)的直線以及點
\(P_1,P_2,...,P_j\)
描述在圖中:
直線自下向上移動,只要它過任何一個點 \(P\) ,它就成為了符合要求的直線。
我們要求截距最小,顯然,當它自下向上移動過的第一個點 \(P_j\) 時,截距最小。如圖,此時能取得截距最小的點是 \(P_2\) 。那麼由上可知, \(j=2\) 時,一次函式的截距最小,更新得到的 \(f_i\) 也是最小的。
所以,我們的目標就轉變為了找到一次函式能夠第一個“碰到”的點。
觀察上圖,我們將最有可能與直線先“碰到”的點(最外圍的點)兩兩相連,發現: 它們近似的構成了一個下凸殼的形狀,兩兩相連的線段所在的直線的斜率依次遞增 。
此時我們發現了一個很好的性質,我們的目標直線第一個過的點最優點 \(P_j\) 滿足: \(P_j,P_{j+1}\) 所在直線是斜率大於目標直線斜率的第一條直線 。( \(P_2,P_3\) 構成的直線的斜率大於圖中直線的斜率,但 \(P_1,P_2\)構成的直線的斜率小於圖中直線的斜率,所以
\(P_2\)
為最優點)
那麼這就成為了我們的突破口了:由於構成下凸殼直線滿足斜率單調遞增,我們用單調佇列維護這些 \(P\) 點。由於隨著i的增加, \(a_i\) 也是單調遞增的,這就應和了單調佇列的操作。
對於每一個 \(i\) ,我們讓斜率小於 \(2a_i\) 的單調佇列中的直線所對應的點出隊(它小於當前的 \(2a_i\) ,由於 \(a_i\) 單調遞增,它也一定小於以後的 \(2a_i\) ,所以這些點將會是一直無用的,可以直接出隊),直到找到第一條斜率大於 \(2a_i\) 的直線,此時,隊頭的點的編號j即為最優決策。我們直接利用該決策轉移。
完成轉移以後,新的點
\(P_i\)
也需要加入佇列裡,此時,我們還要維護一個操作:
當 \(P_i\) (圖中的 \(P_7\) )加入後,我們發現,原來的 \(P_4,P_3\) 構成的直線的斜率大於 \(P_3\) 和新的 \(P_4\) 構成的斜率,這樣, \(P_4\) 就到了內部,新的下凸殼由 \(P_1,P_2,P_3,P_7\) 構成,我們需要讓 \(P_4\) 出隊。
即當 \(slope(q[tail],q[tail-1])>slope(q[tail-1],i)\)(
\(solpe\)
代表斜率函式)時,隊尾出隊。
事實上,我們在不斷維護一個下凸殼的形狀,由於單調佇列一共會進出至多N個點,所以,這樣實現轉移的時間複雜度是 \(O(n)\) 的,我們將此種優化方法稱為斜率優化。
\(Code:\)
#include<bits/stdc++.h> using namespace std; const int N=50000+80; long long f[N],q[N],sum[N],toy[N],n,L,head,tail; inline long long a(long long k){return sum[k]+k;} inline long long b(long long k){return a(k)+L+1;} inline long long x(long long k){return b(k);} inline long long y(long long k){return f[k]+b(k)*b(k);} inline double slope(long long p,long long q){return ((y(p)-y(q))*1.0)/((x(p)-x(q))*1.0);} int main(void) { freopen("toy.in","r",stdin); freopen("toy.out","w",stdout); scanf("%lld%lld",&n,&L); for(int i=1;i<=n;i++) { scanf("%lld",&toy[i]); sum[i]=sum[i-1]+toy[i]; } for(int i=1;i<=n;i++) { while(head<tail&&slope(q[head],q[head+1])<2*a(i))head++; f[i]=f[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head])); while(head<tail&&slope(q[tail],q[tail-1])>slope(q[tail-1],i))tail--; q[++tail]=i; } printf("%lld\n",f[n]); }