bzoj1010: [HNOI2008]玩具装箱toy【斜率优化DP】
第一道斜率优化DP~
朴素的DP方程是比较容易想到的(想不到的话说明基本功还不够,多做一点简单DP题目吧):F[i]表示前i个玩具装好的最小花费,则:
F[i]=min(F[j]+(SUM[i]-SUM[j]+i-j-1-L)^2))。
这里的SUM[i]表示前i个玩具的总长度。
简化一下,用K[i]表示SUM[i]+i,V表示L+1,就可以简化一下方程:
F[i]:=min(F[j]+(K[i]-K[j]-V)^2)
但是这个方程的时间复杂度是O(N^2)的,所以我们需要优化。
首先我们可以证明对于i,有两个决策点j和k(从F[j]和F[k]推过来的状态,j<k),如果k不比j差,也就是说
F[k]+(K[i]-K[k]-V)^2<=F[j]+(K[i]-K[j]-V)^2
可以证明对于后面的任意状态t,有
F[k]+(K[t]-K[k]-V)^2<=F[j]+(K[t]-K[j]-V)^2
通俗地说,就是如果在以前的DP中,存在某一个状态i从状态j转移过来不如从状态k转移过来,则在i后面的任何一个状态t,从状态j转移到状态t不如从状态k转移到状态t。令K[t]=K[i]+C,那么证明:
F[k]+(K[t]-K[k]-V)^2<=F[J]+(K[t]-K[j]-V)^2
F[k]+(K[i]+C-K[k]-V)^2<=F[J]+(K[i]+C-K[j]-V)^2
F[k]+(K[i]-K[k]-V)^2+2*(K[i]-K[k]-V)*C+C^2<=F[j]+(K[i]-K[j]-V)^2+2*(K[i]-K[j]-V)*C+C^2
2*(K[i]-K[K]-V)*C<=2*(K[i]-K[j]-V)*C
K[k]>=K[j]
而因为K[i]显然是单调递增的,所以显然成立。
维护一个单调递增的东东我们可以使用单调队列,但是要维护什么呢?就是这个:
F[k]+(K[i]-K[k]-V)^2<=F[j]+(K[i]-K[j]-V)^2
这是个不等式不能直接维护,并且存在与i有关的东西,对于i来说j和k是已经求出来的东西,我们常用的是将不等式一边用j和k表示,另一边用i表示。这个你们自己化简一下吧经过化简,得到:
(F[k]+(K[k]+V)^2-F[j]-(K[j]+V)^2)/(2*(K[k]-K[j]))<=K[i]
为了简洁一点,可以令
G(k,j)=F[k]+(K[k]+V)^2-F[j]-(K[j]+V)^2
S(k,j)=2*(F[k]-F[j])
X(k,j)=G(k,j)/S(k,j)
所以当我们比较j和k对i的优劣的时候可以比较斜率,用单调队列维护一下就能做到O(1)转移,维护时间复杂度是均摊O(N)的,这样就能解决这个问题。
所以单调队列的维护:
队首:
假设a,b(a<b)是队首元素,若X(b,a)<=K[i],则a比b好,删除a,否则不需维护。
队尾:
假设a,b,c(a<b<c)是队尾元素,若X(b,a)<X(c,b)说明b比c要好,可以保留b,否则c就比b好,就要删去b。
总之代码:
var k,sum,f:array[0..50000]of int64; q:array[0..50000]of longint; n,l,i,j,p,h,t:longint; k1,k2,k3,k4:int64; function g(x,y:longint):int64; begin exit(f[x]+(k[x]-k[y])*(k[x]+l+k[y]+l)-f[y]); end; function s(x,y:longint):int64; begin exit(2*(k[x]-k[y])); end; begin read(n,l); randomize; inc(l); for i:=1 to n do begin read(p); //p:=random(10000000)+1; sum[i]:=sum[i-1]+p; k[i]:=sum[i]+i; end; t:=1; h:=1; for i:=1 to n do begin repeat if h>=t then break; k1:=g(q[h+1],q[h]); k2:=s(q[h+1],q[h]); k3:=k2*k[i]; if k1<=k3 then inc(h); until k1>k3; f[i]:=f[q[h]]+(k[i]-k[q[h]]-l)*(k[i]-k[q[h]]-l); repeat if h>=t then break; k1:=g(q[t],q[t-1]); k2:=s(i,q[t]); k3:=g(i,q[t]); k4:=s(q[t],q[t-1]); if k1/k4>=k3/k2 then dec(t); until k1/k4<k3/k2; inc(t); q[t]:=i; end; writeln(f[n]); end.
PS:斜率优化代码很短,但是有一定的思考难度,总之如果没弄懂也不要急着抄代码,多看几遍也许就可以意会到了。。。
发表回复