洛谷 P3195 [HNOI2008]玩具装箱 题解【斜率优化】【DP】【单调队列】

点击量：202

斜率优化..感觉没学过

目录

题目描述

P 教授要去看奥运，但是他舍不得他的玩具，于是他决定把所有的玩具运到北京。

他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维，再放到一种特殊的一维容器中。P 教授有编号为 $1\dots N$ 的 $N$ 件玩具，玩具经过压缩后会变成一维，第 $i$ 件件玩具压缩后长度为 $C_i$。

为了方便整理，P 教授要求：

• 在一个一维容器中，玩具的编号是连续的；
• 如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中，则容器长度不小于 $x=j-i+ \sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$，其中 $L$ 是一个常量。

P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。试求最小费用。

输入输出格式

输入格式：

第一行输入两个整数 $N,L$。

接下来 $N$ 行输入 $C_i$。

输出格式：

输出最小费用。

输入输出样例

输入样例#1：

5 4
3
4
2
1
4

输出样例#1：

1

数据范围与约定

$1\le N\le 5\times 10^4,1\le L,C_i\le 10^7$

题解

对于这一个过程，有一个比较明显的 $O(n^2)$ dp。

我们首先要把方程写出来，然后再考虑进一步优化。

令 $f[i]$ 表示装好前 $i$ 个玩具的最小费用，$sum[i]$ 表示 $\sum_{j=1}^iC_i$，则
$$
f[i]=\min_{0\le i<j}\left\{f[j]+(i-j-1+sum[i]-sum[j]-L)^2\right\}
$$
我们令 $g[i]=sum[i]+i,l=L+1$，则有
$$
\begin{aligned}
f[i]&=\min_{0\le i<j}\left\{f[j]+(g[i]-g[j]-l)^2\right\}\\
&=\min_{0\le i<j}\left\{f[j]+\left(g^2[i]+g^2[j]+l^2-2g[i]\cdot g[j]-2g[i]\cdot l+2g[j]\cdot l\right)\right\}\\
&=\min_{0\le i<j}\left\{f[j]+g^2[j]-2g[i]\cdot g[j]+2g[j]\cdot l\right\}+g^2[i]+l^2-2g[i]\cdot l
\end{aligned}
$$
但是我们不能忘了本来的目的，就是让 $f[i]$ 最小。那么一定存在一个 $j$ 使得最终的 $f[i]$ 满足
$$
f[i]=f[j]+g^2[j]-2g[i]\cdot g[j]+2g[j]\cdot l+g^2[i]+l^2-2g[i]\cdot l\\
f[j]+g^2[j]+2g[j]\cdot l=2g[i]\cdot g[j]+f[i]-g^2[i]-l^2+2g[i]\cdot l
$$
注意正负号 TAT

此时发现等号左侧全部与 $j$ 有关，右侧仅有一个与 $j$ 有关，而且它还有个特性。即仅有 $2g[i]\cdot g[j]$ 这一项同时和 $i,j$ 有关。

令等式左侧与 $j$ 有关的项之和为 $y$，$2g[i]\cdot g[j]$ 为 $kx$，其余项（不包含 $j$ 的任何项）设为 $b$。

原等式就是 $y=kx+b$ 的形式，其中 $f[i]\propto b$，且比例系数为 $1$，即 $f[i]$ 随 $b$ 的增大而增大，此时我们只需要令 $b$ 尽可能小就可以了。

考虑上面 $y$ 和 $j$ 有关，坐标由 $x,y$ 决定，因此 $x$ 也应该与 $j$ 有关，那么令 $k=2g[i],x=g[j]$。

所以当计算 $f[i]$ 的时候，$k$ 就是一个常数，后面的 $b$ 除了 $f[i]$，剩下的部分也是一个常数。而 $x,y$ 仅跟 $j$ 的取值有关。

对于每个 $j$，在平面直角坐标系中给它一个点，坐标为 $\left(g[j],f[j]+g^2[j]+2g[j]\cdot l\right)$。而随着 $j$ 递增，横坐标 $g[j]=sum[j]+j$ 是在递增的，我们需要找到已知 $k$，使得 $b$ 最小的 $x,y$。

那么我们对之前的点维护一个下凸壳，把斜率为 $k$ 的直线从下往上移，直到和凸壳有交点。而这个交点一定是凸壳的一个顶点。

考虑对于凸壳的维护。当我们 dp 到 $i$ 时，用到的是 $1\sim i-1$ 的凸壳，由于横坐标递增，所以直接用一个单调栈即可。但是我们每次要找到它与斜率为 $k$ 的直线的最低交点，难道要二分吗？

实际上，凸壳中斜率小于 $k$ 的部分是没有用的。因为每次的斜率 $k=2g[i]$，也是在递增，当我们找到符合条件的点时，那些在凸壳上比它低的点都没有用了。

所以我们直接用一个单调队列维护凸壳。发现 $q[l+1],q[l+2]$ 构成的直线的斜率小于 $k$，则弹出 $q[l+1]$。

最终把 $q[l+1]$ 带入 $y=kx+b$，把 $b$ 带入 $b=f[i]-g^2[i]-l^2+2g[i]\cdot l$，得到 $f[i]$。

时间复杂度 $O(n)$。

Code：

#include<cstdio>
#include<cstring>
#define ll long long
ll f[50050],g[50050];
ll x[50050],y[50050];//x,y 存起来优化常数
int q[50050],l=0,r=0;
int main()
{
    int n;
    ll L;
    scanf("%d%lld",&n,&L);
    ++L;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&g[i]);
        g[i]+=g[i-1]+1;
    }
    x[0]=0,y[0]=0;
    q[++r]=0;
    for(int i=1;i<=n;++i)
    {
        ll k=2*g[i];
        while(r-l>=2&&y[q[l+2]]-y[q[l+1]]<k*(x[q[l+2]]-x[q[l+1]]))
            ++l;
        int j=q[l+1];
        f[i]=f[j]+g[i]*g[i]+g[j]*g[j]+L*L-2*g[i]*g[j]-2*L*g[i]+2*L*g[j];
        x[i]=g[i];
        y[i]=f[i]+g[i]*g[i]+2*L*g[i];
        while(r-l>=2&&x[q[r]]*y[i]-x[q[r]]*y[q[r]]-x[q[r-1]]*y[i]+x[q[r-1]]*y[q[r]]<
                    x[i]*y[q[r]]-x[i]*y[q[r-1]]-x[q[r]]*y[q[r]]+x[q[r]]*y[q[r-1]])
            --r;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}