斜率优化dp & Luogu P3195 [HNOI2008]玩具装箱

题目传送门

本题状转方程：

$$\begin{aligned} d_i&=\min_{j<i}\{d_j+(sum_i-sum_j+i-j-1-L)^2\}\\ &=\min_{j<i}\{d_j+((-1-L+sum_i+i)-(j+sum_j))^2\}\\ &设A_i=-1-L+sum_i+i,B_i=i+sum_i\\ &=\min_{j<i}\{d_j+(A_i-B_j)^2\}\\ &=\min_{j<i}\{d_j+B_j^2-2\times A_i \times B_j\}+A_i^2 \end{aligned}$$

推式子的方向是将只含 $j$（决策）的，既含 $j$（决策）又含 $i$（状态）的和不含 $j$ 的分别放在一起。

于是只含 $j$ 的 $d_j+B_j^2$、既含 $j$ 又含 $i$（斜率优化要求含 $i$ 与 $j$ 这一部分中这两者的关系是相乘）的 $2\times A_i \times B_j$、和什么都不含的 $A_i^2$。

只含 $j$ 的部分就是决策点的 $y$ 坐标，既含 $j$ 又含 $i$ 的部分比较复杂：将这一部分分为只含 $i$ 的 $part1$ 和只含 $j$ 的 $part2$（系数归谁无所谓），$part2$ 就是决策点的 $x$ 坐标，而 $part1$ 的相反数是状态线的斜率。本题 $x_i=B_i$，$y_i=d_i+B_i^2$，$k_i=-(-(2\times A_i))=2\times A_i$。

注意：决策点 $x$ 坐标必须满足随状态的下标（$i$）增加而单增。

上（下）凸壳维护即可，二分查询。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 5e4;

template <typename T>
inline void read(T &a) {
    register char c;while (c = getchar(), (c < '0' || c > '9') && c != '-');register bool f = c == '-';register T x = f ? 0 : c - '0';while (c = getchar(), c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48);}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &n, Argv &...argv) {
    read(n), read(argv...);
}

struct Point {
    double x, y;
    int idx;
    inline bool operator<(const Point sec) const {
        if (x == sec.x) {
            return y < sec.y;
        }
        return x < sec.x;
    }
};
inline double k(Point a, Point b) {
    return (b.y - a.y) / (b.x - a.x);
}
inline double cp(Point a1, Point a2, Point b1, Point b2) {
    return (a2.x - a1.x) * (b2.y - b1.y) - (b2.x - b1.x) * (a2.y - a1.y);
}

int n, L, sum[MAXn + 10], d[MAXn + 10];
int top; Point stk[MAXn + 10];
int Div(int l, int r, double x) {
    if (l > r) return r;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (k(stk[mid], stk[mid + 1]) >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

signed main() {
    read(n, L);
    for (int i = 1, a; i <= n; ++i) {
        read(a);
        sum[i] = sum[i - 1] + a;
    }
    stk[++top] = Point{x: 0, y: 0, idx: 0};
    for (int i = 1; i <= n; ++i) {
        int Ai = (-1 - L + sum[i] + i), Bi = i + sum[i];
        int j = Div(1, top - 1, 2 * Ai);
        if (j == 0 || (j == top - 1 && k(stk[top - 1], stk[top]) < 2 * Ai)) {
            j = top;
        }
        j = stk[j].idx;
        int Bj = j + sum[j];
        d[i] = d[j] + (Ai - Bj) * (Ai - Bj);
        Point nowpoint = Point{x: (double)Bi, y: (double)d[i] + Bi * Bi, idx: i};
        while (top > 1 && cp(stk[top - 1], stk[top], stk[top], nowpoint) <= 0) {
            --top;
        }
        stk[++top] = nowpoint;
    }
    printf("%lld\n", d[n]);
}