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:斜率优化代码很短,但是有一定的思考难度,总之如果没弄懂也不要急着抄代码,多看几遍也许就可以意会到了。。。

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据