斜率優(yōu)化dp專題

斜率優(yōu)化dp專題HDU3507,BZOJ101015973437109619113675能用斜率優(yōu)化的dp題一般都需要證明決策單調(diào)性（然而我到現(xiàn)在還沒有搞懂到底何為決策單調(diào)）。一般有幾種思路：1)將得到的數(shù)據(jù)打表，一般打表打[L,R]內(nèi)這一段的值，判斷是否基本滿足四邊形不等式：的模樣，或者還有敲暴力之后看看dp數(shù)組內(nèi)的值是否單調(diào)。2)在敲暴力的過程中能感覺到，需要從前面已經(jīng)得到的結(jié)果查找最優(yōu)解，但是這個最優(yōu)解在一定范圍內(nèi)，而不必全部找過來的時候，就可能需要用上優(yōu)化了。3)重要的是如果能寫出《1D1D》中的經(jīng)典模型的形式：f(x)=minx?1i=1{f(i)+w[i,x]}那幾乎就可以確定出題人就在考斜率優(yōu)化dp。一旦確定這題可以用斜率優(yōu)化dp做，那么題目就變成了板子題。按我最近刷這類題目的方法來看，其實只要拆分成下面幾步就可以做：1)對題目進(jìn)行單調(diào)性分析并且列出轉(zhuǎn)移方程式。由于最近刷的題目早就知道是斜率優(yōu)化所以沒有分析單調(diào)性，而單調(diào)性的得出還是需要轉(zhuǎn)移方程式輔助。由于O(n)的平攤復(fù)雜度需要用到單調(diào)隊列deque，我們需要針對縮進(jìn)front指針和rear指針的兩個while操作進(jìn)行設(shè)計函數(shù)：（就以上面提及的標(biāo)準(zhǔn)函數(shù)為例）2)為了使隊列中的deq[L]彈出，就需要deq[L]不比dep[L+1]優(yōu)：設(shè)i,j,k滿足條件j<k<i，且i從j轉(zhuǎn)移比從k轉(zhuǎn)移優(yōu)，則可以列出等式：通過對該式子分離出帶有i的變量，可以得到一個解題最重要的不等式（斜率優(yōu)化的代碼辣么短都是因為這個不等式的關(guān)系）。如果提取不出上述要求的不等式就不能用斜率優(yōu)化dp解題。最后就能精簡出一個函數(shù)g(x,y)滿足g(x,y)<=w[i]。但是我并不建議實際代碼寫成g(x,y)。3)為了使隊列中的deq[R]彈出，就需要deq[R]對于deq[R?1]和i都不優(yōu)：設(shè)a,b,c滿足條件a<b<c<i，如果滿足：則deq[R]不優(yōu)。因為當(dāng)g(deq[R?1],deq[R])<=w[i]時，deq[R?1]更優(yōu)；當(dāng)g(deq[R?1],deq[R])>w[i]時，g(dep[R],i)>w[i]，i更優(yōu)。所以一個斜率優(yōu)化的dp的重點在于g(x,y)的推導(dǎo)（不是很喜直線方程的寫法）以及兩個縮進(jìn)while語句的符號問題（反正只要考慮左側(cè)的要求能夠傳遞到右側(cè)而不會改變即可）。斜率優(yōu)化dp應(yīng)用舉例：斜率優(yōu)化dp應(yīng)用舉例BZOJ1010HNOI2008玩具裝箱toyBZOJ1597USACO2008土地并購HDU3507PrintArticleBZOJ3437小P的牧場BZOJ1096ZJOI2007倉庫建設(shè)BZOJ1911Apoi2010特別行動隊BZOJ3675Apio2014序列分割BZOJ1010HNOI2008玩具裝箱toyDescriptionP教授要去看奧運，但是他舍不下他的玩具，于是他決定把所有的玩具運到北京。他使用自己的壓縮器進(jìn)行壓縮，其可以將任意物品變成一堆，再放到一種特殊的一維容器中。P教授有編號為1…N的N件玩具，第i件玩具經(jīng)過壓縮后變成一維長度為Ci。為了方便整理，P教授要求在一個一維容器中的玩具編號是連續(xù)的。同時如果一個一維容器中有多個玩具，那么兩件玩具之間要加入一個單位長度的填充物。形式地說如果將第i件玩具到第j個玩具放到一個容器中，那么容器的長度將為x=j?i+∑jk=iCk。制作容器的費用與容器的長度有關(guān)，根據(jù)教授研究，如果容器長度為x，其制作費用為(x?L)2，其中L是一個常量。P教授不關(guān)心容器的數(shù)目，他可以制作出任意長度的容器，甚至超過L。但他希望費用最小。我們可以得到滿足樣例的結(jié)果是分成{1},{2},{3,4},{5}四組，并且我們也可以發(fā)現(xiàn)這個表格是滿足四邊形不等式的。首先考慮采用O(logn)的單調(diào)棧完成這個題目。我們考慮當(dāng)前的dp(i)能夠去更新哪些點，那么能夠更新的點就會形成一段區(qū)間。我們在棧中存儲的值是每個不同的dp(i)所能更新的區(qū)間左端點，而右端點則是接下來的一個左端點（棧頂?shù)挠叶它c是n），可更新的最優(yōu)區(qū)間就是[stk[i],str[i+1])。查找結(jié)果的時候，我們只需要用二分查找找到包含該位置的最優(yōu)區(qū)間；更新最優(yōu)解的時候，始終考慮以該點作為更新點，可以更新到的離n的最遠(yuǎn)點在哪里。如果比當(dāng)前的區(qū)間還優(yōu)（即用當(dāng)前區(qū)間的更新點不比用dp[i]優(yōu)），將其覆蓋；否則只會優(yōu)于當(dāng)前區(qū)間的部分區(qū)間，滿足01性，同樣通過二分查找可以找到結(jié)果。平攤的復(fù)雜度最大就是O(logn)。我寫O(nlogn)的時候反而比O(n)卡了更久，沒有搞明白區(qū)間和更新點之間的關(guān)系，但是搞明白之后對單調(diào)性有更清楚的認(rèn)識。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM50005intn,Len,stk[M],pre[M],top=0;longlongsum[M],dp[M];longlongsqr(longlongx){returnx*x;}longlongcalc(intL,intR){returndp[L]+sqr(R-L-1+sum[R]-sum[L]-Len);}intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}/*for(inti=0;i<n;i++){for(intj=i+1;j<=n;j++)printf("[%d,%d]%lld",i,j,calc(i,j));puts("");}//打印出w[i,j]，觀察答案與單調(diào)性*/dp[0]=0;stk[++top]=0;pre[top]=0;for(inti=1;i<=n;i++){intL=1,R=top,res=0;while(L<=R){intmid=L+R>>1;if(stk[mid]<=i){res=mid;L=mid+1;}elseR=mid-1;}dp[i]=calc(pre[res],i)while(top&&i<stk[top]&&calc(pre[top],stk[top])>calc(i,stk[top]))--top;L=stk[top],R=n,res=n+1;while(L<=R){intmid=L+R>>1;if(calc(pre[top],mid)>calc(i,mid)){res=mid;R=mid-1;}elseL=mid+1;}if(res!=n+1){//當(dāng)i根本不優(yōu)的時候不能插入istk[++top]=res;pre[top]=i;}}printf("%lld\n",dp[n]);}嘗試推一下g(x,y)函數(shù)：此處還要注意有兩種寫法，一種是采用double的g(x,y)寫法，一種是將分子分母分離交叉相乘的寫法，但是g(x,y)寫法的缺點是會出現(xiàn)分母為0的情況需要特判，一個不小心還會出現(xiàn)精度問題。從速度上來講，用除法顯然比用乘法慢（在BZOJ上親測用g(x,y)慢了50+ms）。/*g(x,y)寫法*/#defineM50005intn,Len;longlongdp[M],sum[M];longlongsqr(longlongx){returnx*x;}doubleg(intx,inty){return(dp[y]+sqr(sum[y]+y+Len+1)-dp[x]-sqr(sum[x]+x+Len+1))/(2.0*(sum[y]-sum[x]+y-x));}intdeq[M],L=0,R=-1;intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&g(deq[L],deq[L+1])<=sum[i]+i)++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]]+i-deq[L]-1-Len);while(L<R&&g(deq[R-1],deq[R])>g(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}/*分離分子分母的寫法*/#defineM50005intn,Len;intdeq[M],L=0,R=-1;longlongdp[M],sum[M];longlongsqr(longlongx){returnx*x;}longlongup(intx,inty){returndp[y]-dp[x]+sqr(sum[y]+y+Len+1)-sqr(sum[x]+x+Len+1);}longlongdown(intx,inty){return2*(sum[y]-sum[x]+y-x);}intmain(){scanf("%d%d",&n,&Len);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<=(sum[i]+i)*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]]+i-deq[L]-1-Len);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1597USACO2008土地并購DescriptionKano準(zhǔn)備擴(kuò)大他的農(nóng)場，眼下必須購買N塊長方形土地。如果Kano買一塊土地，價格就是土地的面積。他也可以選擇并購一塊土地，并購的價格為這些土地中最大的長乘以最大的寬，比如Kano購買3x5和5x3的土地，只需要支付5x5=25元，比分開買合算。請你幫他計算購買所有土地的最小費用。SampleInput&Output4100115152051100500啊啊，先膜一下“水”大犇。題目描述只是因為我把這題搬到自家oi上的。在寫本題的O(n^2)暴力dp的時候有沒有想過常數(shù)優(yōu)化？畢竟那些長寬小于某一塊土地的都對答案沒啥貢獻(xiàn)，可以算是附贈的。而且如果在一維有序的情況下只需要理論下限的O(n)復(fù)雜度就可以過掉了。那么此題的轉(zhuǎn)移就很顯然了：將兩者都倒序枚舉，除去干擾單調(diào)性的數(shù)據(jù)，則長單調(diào)遞減，寬單調(diào)遞增?？梢缘玫睫D(zhuǎn)移方程：structnode{inth,w;booloperator<(constnode&cmp)const{if(h!=cmp.h)returnh>cmp.h;returnw>cmp.w;}}Base[M],Q[M];intqtop=0;intdeq[M],L=0,R=-1;longlongdp[M];longlongup(intx,inty){returndp[y]-dp[x];}longlongdown(intx,inty){returnQ[x+1].h-Q[y+1].h;}intmain(){intn;scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d%d",&Base[i].h,&Base[i].w);sort(Base+1,Base+n+1);intw=0;for(inti=1;i<=n;i++){if(Base[i].w<=w)continue;Q[++qtop]=Base[i];w=Base[i].w;}n=qtop;deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<Q[i].w*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+1LL*Q[deq[L]+1].h*Q[i].w;while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}HDU3507PrintArticleDescriptionKano想要打印一篇含有N個單詞的文章，每個單詞的打印費用是Ci，一行打印k個單詞的費用是：#include<cstdio>#include<cstring>#include<algorithm>#defineM500005usingnamespacestd;intsum[M],dp[M],deq[M];intsqr(intx){returnx*x;}intup(intx,inty){return(sqr(sum[y])-sqr(sum[x])+dp[y]-dp[x]);}intdown(intx,inty){return2*(sum[y]-sum[x]);}intmain(){intn,Mt;while(scanf("%d%d",&n,&Mt)==2){for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}intL=0,R=-1;deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<=sum[i]*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+sqr(sum[i]-sum[deq[L]])+Mt;while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}printf("%d\n",dp[n]);}return0;}BZOJ3437小P的牧場Description小P在MC里有n個牧場，自西向東呈一字形排列（用1…n編號），于是他就煩惱了：為了控制這n個牧場，他需要在某些牧場上面建立控制站。每個牧場上只能建立一個控制站，每個控制站控制的牧場是它所在的牧場一直到它西邊第一個控制站的所有牧場（它西邊第一個控制站所在的牧場不被控制；如果它西邊不存在控制站，那么它控制西邊所有的牧場）。每個牧場被控制都需要一定的花費，而且該花費等于它到控制它的控制站之間的牧場數(shù)目（不包括自身，但包括控制站所在牧場）乘上該牧場的放養(yǎng)量，在第i個牧場建立控制站的花費是ai，每個牧場i的放養(yǎng)量是bi，理所當(dāng)然，小P需要總花費最小，但是小P的智商有點不夠用了，所以這個最小總花費就由你來算出啦。SampleInput&Output4242431429這個題目稍微不水的地方莫非是如何用連續(xù)和求出第i個控制站控制前面牧場的所用費用？hwzer大犇說正推比較煩。個人不怎么覺得……我們先看一下w[i,j]=∑jk=i{B[k]?(j?k)}=∑jk=i{B[k]?j?B[k]?k}，前半部分采用正常的前綴和相減再乘以j得到，而后半部分維護(hù)一個相同模樣的前綴和即可。方程：#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM1000005intA[M],B[M];longlongsum1[M],sum2[M],dp[M];intdeq[M],L=0,R=-1,n;longlongcalc(intL,intR){returndp[L]+A[R]+(sum1[R]-sum1[L])*R-(sum2[R]-sum2[L]);}longlongup(intL,intR){returndp[R]-dp[L]+sum2[R]-sum2[L];}longlongdown(intL,intR){returnsum1[R]-sum1[L];}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&A[i]);for(intj=1;j<=n;j++)scanf("%d",&B[j]);for(intj=1;j<=n;j++){sum1[j]=sum1[j-1]+B[j];sum2[j]=sum2[j-1]+1LL*B[j]*j;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<i*down(deq[L],deq[L+1]))++L;dp[i]=calc(q[L],i);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=down(deq[R-1],deq[R])*up(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1096ZJOI2007倉庫建設(shè)DescriptionL公司有N個工廠，由高到底分布在一座山上,工廠1在山頂，工廠N在山腳。由于這座山處于高原內(nèi)陸地區(qū)（干燥少雨），L公司一般把產(chǎn)品直接堆放在露天，以節(jié)省費用。突然有一天，L公司的總裁L先生接到氣象部門的電話，被告知三天之后將有一場暴雨，于是L先生決定緊急在某些工廠建立一些倉庫以免產(chǎn)品被淋壞。由于地形的不同，在不同工廠建立倉庫的費用可能是不同的。第i個工廠目前已有成品Pi件，在第i個工廠位置建立倉庫的費用是Ci。對于沒有建立倉庫的工廠，其產(chǎn)品應(yīng)被運往其他的倉庫進(jìn)行儲藏，而由于L公司產(chǎn)品的對外銷售處設(shè)置在山腳的工廠N，故產(chǎn)品只能往山下運（即只能運往編號更大的工廠的倉庫），當(dāng)然運送產(chǎn)品也是需要費用的，假設(shè)一件產(chǎn)品運送1個單位距離的費用是1。假設(shè)建立的倉庫容量都都是足夠大的，可以容下所有的產(chǎn)品。在每一行，你都將得到以下數(shù)據(jù)：1.工廠i距離工廠1的距離Xi（其中X1=0）2.工廠i目前已有成品數(shù)量Pi3.在工廠i建立倉庫的費用Ci請你幫助L公司尋找一個倉庫建設(shè)的方案，使得總的費用（建造費用+運輸費用）最小。SampleInput&Output3051053100961032同上，水題（直接復(fù)制的，改下就A了）。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineM1000005intX[M],A[M],B[M];longlongsum1[M],sum2[M],dp[M];intdeq[M],L=0,R=-1,n;longlongcalc(intL,intR){returndp[L]+A[R]+(sum1[R]-sum1[L])*X[R]-(sum2[R]-sum2[L]);}longlongup(intL,intR){returndp[R]-dp[L]+sum2[R]-sum2[L];}longlongdown(intL,intR){returnsum1[R]-sum1[L];}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d%d%d",&X[i],&B[i],&A[i]);for(intj=1;j<=n;j++){sum1[j]=sum1[j-1]+B[j];sum2[j]=sum2[j-1]+1LL*B[j]*X[j];}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])<X[i]*down(deq[L],deq[L+1]))++L;dp[i]=calc(deq[L],i);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=down(deq[R-1],deq[R])*up(deq[R],i))--R;deq[++R]=i;}printf("%lld\n",dp[n]);return0;}BZOJ1911Apoi2010特別行動隊DescriptionSampleInput&Output4-110-2022349這里要注意的是a<0，所以如果寫成g(x,y)的形式要小心。方程：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#defineM1000005usingnamespacestd;intn,a,b,c;longlongsum[M],dp[M];longlongsqr(longlongx){returnx*x;}longlongcalc(longlongx){returna*sqr(x)+b*x+c;}longlongup(intx,inty){returndp[y]-dp[x]+a*sqr(sum[y])-a*sqr(sum[x])+b*(sum[x]-sum[y]);}longlongdown(intx,inty){return2*a*(sum[y]-sum[x]);}intdeq[M],L=0,R=-1;intmain(){scanf("%d%d%d%d",&n,&a,&b,&c);for(inti=1,x;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}deq[++R]=0;for(inti=1;i<=n;i++){while(L<R&&up(deq[L],deq[L+1])>=sum[i]*down(deq[L],deq[L+1]))++L;dp[i]=dp[deq[L]]+calc(sum[i]-sum[deq[L]]);while(L<R&&up(deq[R-1],deq[R])*down(deq[R],i)>=up(deq[R],i)*down(deq[R-1],deq[R]))--R;deq[++R]=i;}cout<<dp[n]<<endl;}BZOJ3675Apio2014序列分割Description小H最近迷上了一個分隔序列的游戲。在這個游戲里，小H需要將一個長度為n的非負(fù)整數(shù)序列分割成k+1個非空的子序列。為了得到k+1個子序列，小H需要重復(fù)k次以下的步驟：1.小H首先選擇一個長度超過1的序列（一開始小H只有一個長度為n的序列，也就是一開始得到的整個序列）；2.選擇一個位置，并通過這個位置將這個序列分割成連續(xù)的兩個非空的新序列。每次進(jìn)行上述步驟之后，小H將會得到一定的分?jǐn)?shù)。這個分?jǐn)?shù)為兩個新序列中元素和的乘積。小H希望選擇一種最佳的分割方式，使得k輪之后，小H的總得分最大。SampleInput&Output734134023108二維的斜率優(yōu)化題。這題的難點在于如何理解最后得到的分?jǐn)?shù)與切的順序無關(guān)。可以這么想：從某段序列中間切一刀，兩邊和相乘，看做左邊的每小段區(qū)間和右邊的每小段區(qū)間分別相乘。異側(cè)的區(qū)間處理完了，接下來就要處理同側(cè)的區(qū)間，此時就采用分治的思想，將問題劃歸到左區(qū)間