洛谷P3195 [HNOI2008]玩具装箱 题解

题目链接：P3195 [HNOI2008]玩具装箱

题意：

有 $n$ 个玩具，第 $i$ 个玩具的价值为 $c_i$ 。要求将这 $n$ 个玩具排成一排，分成若干段。对于一段 $[l,r]$ ，它的代价为 $(r-l+\sum_{i=l}^{r}c_i-L)^2$ ，其中 $L$ 为一个常量，求分段的最小代价。

$1 \leq n \leq 5 \times 10^4$，$1 \leq L \leq 10^7$，$1 \leq C_i \leq 10^7$

upd. 新增斜率优化新的理解。

令 $f_i$ 表示前 $i$ 个物品分成若干段的最小代价，则

$$f_i = \min_{j < i}\left\{f_j + (S_i + i -S_j -j -L-1)^2\right\}$$

其中 $S_i$ 为前 $i$ 个物品的价值和，即 $S_i = \sum_{j=1}^{i}c_j$

直接去做是 $O(n^2)$ ，考虑斜率优化

令 $a_i = S_i + i,~b_i = S_i + i + L+1$ ，则

$$\begin{aligned} f_i &= \min_{j < i}\left\{ f_j + (a_i-b_j)^2 \right\} \\&=\min_{j < i}\left\{ f_j + a_i^2 - 2a_ib_j + b_j^2\right\} \end{aligned}$$

移项得

$$f_i - a_i^2 = \min_{j < i}\left\{ f_j -2a_ib_j + b_j^2\right\}$$

注意到右边的部分有一个 $2a_i$ 导致我们无法单调队列优化

但是我们可以斜率优化，也就是吧 $2a_i$ 看作 $k$

根据斜截式方程可得

$$b=y-kx$$

可知

$$\begin{aligned} b^\prime_i&=f_i-a_i^2 \\k_i&=2a_i \\x_j&=b_j \\y_j &= f_j + b_j^2 \end{aligned}$$

则转移方程可以写成如下形式

$$b_i^\prime = \min\left\{ y_j-k_ix_j\right\}$$

把 $(x_j,y_j)$ 映射到平面上的点，那么问题就转化为了

找到一个 $1\le j<i$ 最小化过点 $(x_j,y_j)$ 且斜率为 $k_i$ 的直线的 $y$ 轴截距

由于这个 $k_i$ 是严格单调递增的，

不难发现这个点一定在 $(x_j,y_j)$ 点集形成的下凸壳上，

并且这个点 $P_j$ 的 $j$ 是满足直线 $P_jP_{j+1}$ 的斜率 $k_j^{\prime}>k_i$ 最小的 $j$

或者说，这个点和下一个在下凸壳上的点所连产生的直线是第一个斜率比 $k_i$ 大的

考虑如何维护这个下凸壳

刚才我们也说了 $k_i$ 是单调递增的，所以这个下凸壳是一个“动态”的

当凸壳上的某个点 $u$ 和下一个点 $v$ 所成的直线斜率小于 $k_i$ 时，

$u$ 就没用了，该被踢掉了

因此我们可以用单调队列来维护，而不是单调栈

然后每次加点就和二维凸包那个差不多，这里不细讲了（

---

对于斜率优化，还有另一种理解

首先刚刚的柿子还是要用到的

$$f_i-a_i^2=\min_{j < i}\left\{ f_j - 2a_ib_j + b_j^2\right\}$$

我们不用刚刚那个

考虑一个 $j~(j>k)$ 在什么情况下比 $k$ 优

显然有

$$f_j-2a_ib_j+b_j^2 < f_k-2a_ib_k+b_k^2$$

然后推推柿子

$$f_j+b_j^2-f_k-b_k^2 < 2a_i(b_j-b_k)$$

注意到 $b_i = S_i + i + L+1$ 是单调递增的

因此有 $b_j > b_k$

则柿子可以化简为

$$\dfrac{f_j+b_j^2-f_k-b_k^2}{b_j-b_k} < 2a_i$$

左边这个东西长的很像斜率的定义

因此我们可以维护一个点集，然后两两点去判断

但是这样肯定是不优的

仔细思考一下，可能成为答案的点一定在这个点集的下凸壳上（因为我们要最小化 $ f_j - 2a_ib_j + b_j^2$ ，所以是下凸壳）

于是我们维护一个下凸壳，依次加入点，再踢出那些不优的点

---

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e4+15)
int n,L;
double sum[N],dp[N];
int st,en,q[N];
double a(int i){return sum[i]+i;}
double b(int i){return a(i)+L+1;}
double X(int i){return b(i);}
double Y(int i){return dp[i]+b(i)*b(i);}
double slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> L;
    for(int i=1; i<=n; i++)
    {
        cin >> sum[i];
        sum[i]+=sum[i-1];
    }
    st=en=1;
    for(int i=1; i<=n; i++)
    {
        while(st<en&&slope(q[st],q[st+1])<2*a(i))++st;
        dp[i]=dp[q[st]]+(a(i)-b(q[st]))*(a(i)-b(q[st]));
        while(st<en&&slope(i,q[en-1])<slope(q[en-1],q[en]))--en;
        q[++en]=i;
    }
    cout << (int)dp[n] << '\n';
    return 0;
}