模板题

P3195 [HNOI2008]玩具装箱

题意:将一段序列 c_i 分成若干段,每一段的代价为 (j-i+\sum_{k=i}^jc_k-L)^2,求最小总代价。

不难发现状态转移方程为

f_i=\min_{j<i}\lbrace f_j+(s_i-s_j+i-j-1-L)^2\rbrace

其中 s_i=\sum_{k=1}^ic_k。时间复杂度为 n^2,考虑进行优化。

为了简化方程,不妨采用参变分离的思想,将只与 i 有关的 s_i+i 令为 a_i,将只与 j 有关的 s_j+j+L+1 令为 b_j,现在的方程为

f_i=\min_{j<i}\lbrace f_j+(a_i-b_j)^2\rbrace

理一下思路:现在我们需要找到一个最优的 j,使得 f_i 达到最优,注意到此时所有关于 i 的量都是确定的。

去掉 min 然后化简转移方程可得:

2a_ib_j+f_i-a_i^2=f_j+b_j^2

斜率优化的精髓,就是要把转移方程化为直线方程 y=kx+b 的形式然后使用数据结构维护一个凸壳。下面来实现这个过程。

一般地,我们将所有只跟 j 有关的项 f_1(j) 看作 y将所有只跟 i 有关的项f_2(i) 看作截距 b,会剩下一项 f_3(i)f_4(j),考虑将 f_3(i) 看作斜率 kf_4(j) 看作 x

这里就是 f_j+b_j^2=yb_j=x

方程化作

2a_ix+f_i-a_i^2=y

注意到除 f_i 以外的与 i 有关的项都是确定的,所以现在的问题就是在坐标系中找到这个 (x,y) 使直线的截距最小(因为要最小化 f_i)。用含 j 的形式方便理解的话就是找到过确定(b_j,f_j+b_j^2) 的斜率为 2a_i 的直线的最小截距。

怎么找呢?看下面的图:
寻找最优的截距

很显然,B 点是我们的最优选择,至于 A 点,因为我们的斜率 k=2a_i 满足单调递增,所以可以让 A 点滚蛋了,至于 C 点,如果我们当前的斜率足够大:

现在 C 点为最优决策点

B 点这辈子以后也不可能用到了,可以让他拜拜了。

插入定义 \operatorname{slope}(A,B) 为直线 AB 的斜率

我们不难发现这样的性质:为了让我们使用的决策点 (b_j,f_j+b_j^2) 最优,我们需要让这些可供选择的决策点形成一个凸壳,即形式化地,设我们维护的这些点序列为 \lbrace P_i\rbrace,且要求 P_1 为需要的决策点,则一定要有 \operatorname{slope}(P_{i-1},P_i)<\operatorname{slope}(P_i,P_{i+1}),即相邻两点间的斜率要单调递增。

同时如果 \operatorname{slope}(P_1,P_2)<k,则选择 P_1 一定不优(在坐标系里面画图可以感受一下),需要弹掉这些点。

做完决策(即求出 f_i 之后),我们需要将 (b_i,f_i+b_i^2) 放入这个序列的末尾,但是还是要满足凸壳的性质。因此考虑用单调队列维护这些点。

for(int i=1;i<=n;++i)
    {
        while(head<tail&&slope(q[head],q[head+1])<2*a[i])//这里是一开始的弹点操作
            ++head;
        int j=q[head];
        f[i]=f[j]+(a[i]-b[j])*(a[i]-b[j]);//进行决策
        while(head<tail && slope(i,q[tail-1])<slope(q[tail-1],q[tail]))//弹尾部的点维护凸性
            --tail;
        q[++tail]=i;//加入凸壳
    }

整道题的代码就是:

#include <cstdio>
#include <cctype>

const int maxn=5e4+5;
int n;
double a[maxn],b[maxn],f[maxn],sum[maxn],L;
int q[maxn],head,tail;

inline double X(int x){return b[x];}
inline double Y(int x){return f[x]+b[x]*b[x];}
inline double slope(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));}

inline int read()
{...}

int main()
{
    n=read(),L=read();
    for(int i=1;i<=n;++i)
    {
        sum[i]=sum[i-1]+read();
        a[i]=sum[i]+i;
        b[i]=sum[i]+i+L+1;
    }
    b[0]=sum[0]+0+L+1;//注意,b_0 不等于 0
    head=tail=1;
    for(int i=1;i<=n;++i)
    {
        while(head<tail&&slope(q[head],q[head+1])<2*a[i])
            ++head;
        int j=q[head];
        f[i]=f[j]+(a[i]-b[j])*(a[i]-b[j]);
        while(head<tail && slope(i,q[tail-1])<slope(q[tail-1],q[tail]))
            --tail;
        q[++tail]=i;
    }
    printf("%lld\n",(long long)f[n]);//观察数据范围发现这东西会爆int
    return 0;
}

总结

对于形如 f_i=\min_{j<i}\lbrace f_j-a_id_j\rbrace,且 a_id_i 满足单调递增的状态转移方程,我们可以使用斜率优化将其从朴素的 O(n^2) 优化到 O(n)

具体地,我们将其看作一条直线方程的形式:f_j=f_i+a_id_j,将 f_j 看作 yd_j 看作 xa_i 看作斜率 kf_i 看作截距。我们就可以利用其单调性维护一个凸壳,来起到加速转移的效果。

步骤一般是如下三步:

  • 弹出队首的点,找到最优决策点 j
  • 根据转移方程算出 f_i
  • 维护凸壳的右端

其他例题

P2365 任务安排

P2365

由于每次开机都需要启动时间 s,维护之前开了几次机比较麻烦,所以考虑开机对后面的任务产生的贡献,即为 s(v_n-v_j)

t_i 为时间的前缀和,v_i 为代价的前缀和)

转移方程即为

f_i=\min_{j<i}\lbrace f_j+t_i(v_i-v_j)+s(v_n-v_j)\rbrace

化简可得 f_j=(t_i+s)v_j+f_i-t_iv_i-sv_n,注意到 v_jt_i+s 都满足单调递增性,所以可以使用斜率优化。

ll f[maxn],t[maxn],s[maxn],n,st;
int q[maxn],head,tail;

inline double Y(int i){return (double)f[i];}
inline double X(int i){return (double)s[i];}
inline double slope(int a,int b){return (Y(a)-Y(b))/(X(a)-X(b));}

int main()
{
    head=tail=1;
    n=read(),st=read();
    for(int i=1;i<=n;++i)
        t[i]=t[i-1]+read(),s[i]=s[i-1]+read();
    for(int i=1;i<=n;++i)
    {
        double k=t[i]+st;
        while(head<tail && slope(q[head],q[head+1])<k)++head;
        f[i]=f[q[head]]+t[i]*(s[i]-s[q[head]])+st*(s[n]-s[q[head]]);
        while(head<tail && slope(q[tail-1],q[tail])>slope(q[tail-1],i))--tail;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

P5017 摆渡车

打完这道题之后对斜率优化理解会更深刻

注意边界,特判横坐标相等的斜率,以及单调队列种一开始的元素

最后修改日期:2020年12月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。