【BZOJ】1010 [HNOI2008] 玩具装箱toy dp+斜率优化

2/22/2017来源:ASP.NET技巧人气:935

题目我就不再赘述了,题目传送门

首先我们先来了解一下斜率优化的用处:斜率优化就是把一些特殊的dp方程化简、变形,然后用维护单调队列,把O(n^2)的时间复杂度降至O(n),实现程序的提速。

当然有些dp方程是无法用斜率优化的,这个我等下会进行详细解释的。

题目中最基本的dp方程可以很容易的想到:f[i]=min{f[j]+(i-(j+1)+s[i]-s[j]-L)^2} (0<=j<i) 其中s[i]表示Sigma(c[k]) (1<=k<=i)

我们设p[i]=s[i]+iM=L+1,则原方程可以转化成f[i]=min{f[j]+(p[i]-p[j]-M)^2} (0<=j<i)

则:f[i]=min{f[j]+p[i]^2-2*p[i]*(p[j]+M)+(p[j]+M)^2} (0<=j<i)

若k<j且j的决策比k要好,则:f[j]+p[i]^2-2*p[i]*(p[j]+M)+(p[j]+M)^2<f[k]+p[i]^2-2*p[i]*(p[k]+M)+(p[k]+M)^2

化简,得:f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2<2*p[i]*(p[j]-p[k])

不等式两边同时除以2*(p[j]-p[k]),得:(f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2)/(2*(p[j]-p[k]))<p[i] 

(f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2)/(2*(p[j]-p[k]))就是斜率g(j,k)

因为s[i]是严格单调上升的,所以p[i]也是严格单调上升的。若p[i]不是严格单调上升的,那么原dp方程就无法用斜率优化,因为原dp方程不满足单调队列的单调性。

所以,知道g(j,k)后,我们可以O(1)判断出j比k更优。

但是,知道g(j,k)后我们并不能把时间复杂度降到O(n),我们还需要一个强有力的帮手:单调队列。

dui[]表示单调队列,t为队头,w为队尾。

1、循环,若g(dui[t+1],dui[t])<p[i],说明dui[t+1]这个决策对于i来说要比dui[t]优,又因为p[i]是严格单调上升的,所以dui[t]这个决策对于后面的所有状态均不产生影响,因此可以将dui[t]弹出单调队列。循环结束后,可根据dui[t]算得f[i]。

2、循环,若g(i,dui[w])<g(dui[w],dui[w-1]):

1)若g(i,dui[w])<g(dui[w],dui[w-1])<p[i],可得g(i,dui[w])<p[i],所以决策i要优于决策dui[w],所以dui[w]这个决策对于后面的所有状态均不产生影响,因此可以将dui[w]弹出单调队列。

2)若p[i]<g(i,dui[w])<g(dui[w],dui[w-1]),可得决策dui[w]优于决策i,决策dui[w-1]优于决策dui[w],所以dui[w]这个决策对于后面的所有状态同样均不产生影响,因此可以将dui[w]弹出单调队列。

综上所述,首先求出斜率g(j,k),然后维护单调队列,依次算出f[],答案即为f[n]。

附上AC代码:

#include <cstdio>
using namespace std;
 
long long n,m,a[50010],s[50010],f[50010],p[50010],dui[50010],t,w;
 
long long min(long long a,long long b){
    return a<b?a:b;
}
 
long long calc(int x,int y){
    return (f[x]+(p[x]+m)*(p[x]+m)-f[y]-(p[y]+m)*(p[y]+m))/(2*(p[x]-p[y]));
}
 
int main(void){
    scanf("%lld%lld",&n,&m);++m;
    for (int i=1; i<=n; ++i)
        scanf("%lld",&a[i]),s[i]=s[i-1]+a[i],p[i]=s[i]+i;
    dui[t=w=1]=0;
    for (int i=1; i<=n; ++i){
        while (t<w&&calc(dui[t+1],dui[t])<=p[i]) ++t;
        int k=dui[t];
        f[i]=f[k]+(p[i]-p[k]-m)*(p[i]-p[k]-m);
        while (t<w&&calc(i,dui[w])<calc(dui[w],dui[w-1])) --w;
        dui[++w]=i;
    }
    PRintf("%lld",f[n]);
    return 0;
}写在最后:虽说这题是斜率优化的入门题,但是要真正弄明白也是不容易的。希望读者们能多加思考,并AC这题。