「HNOI2008」玩具装箱

传送门
Luogu

解题思路

\(\text{DP}\) 很显然：
设 \(dp_i\) 表示前 \(i\) 个玩具的最小费用，转移就是：
\(dp_i = \max\limits_{0\le j < i}\left\{dp_j+(i-j-1+s_i-s_j-L)^2\right\}\)
\(s_i=\sum_{j=1}^ic_j\)，但这是 \(O(n^2)\) 的，显然不够优秀，考虑进一步优化。
我们可以化简一下这个式子：
假设 \(dp_i\) 成功从 \(dp_j\) 转移过来，那么就有：
\(dp_i=dp_j+(i-j-1+s_i-s_j-L)^2\)
整理一下式子：
设 \(a_i = s_i+i-L-1,b_i=s_i+i\)
那么就有：
\(dp_i=dp_j+(a_i-b_j)^2\)
展开并移项可得：
\(dp_j+b_j^2=2a_ib_j+dp_i-a_i^2\)
再设 \(x_i=2b_i,y_i=dp_i+b_i^2\)
\(y_j=a_ix_j+dp_i-a_i^2\)
又因为 \(a_i^2\) 是定值，要最小化 \(dp_i\) ，那么就相当于坐标系中一条斜率为 \(a_i\) 的经过点 \((x_j, y_j)\) ，使得它的纵截距最小化。
又因为我们的 \(a_i, b_i\) 都是递增的，显然这些可能的转移点都要在下凸壳上才能使截距最小。
所以我们用单调队列，维护一下凸包上的转移点。
当前最优转移点从队头不断弹出不最优的点，并用最后的合法情况转移 \(dp_i\)。
插入当前的 \(i\) 时，为了确保凸包的性质，先不断从队尾弹出不合法的点，再插入 \(i\)。
最后输出答案 \(dp_n\)。

细节注意事项

• 咕咕咕

参考代码

#include <algorithm>
#include <iostream>
#include <cstdio>
#define rg register
using namespace std;

typedef double db;
const int _ = 50010;

int n, L; db dp[_], s[_], A[_], B[_];
int hd = 1, tl = 1, Q[_];

inline db X(int i) { return (db) B[i]; }

inline db Y(int i) { return (db) dp[i] + B[i] * B[i]; }

inline db slope(int i, int j) { return (db) (Y(j) - Y(i)) / (X(j) - X(i)); }

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    scanf("%d%d", &n, &L);
    for (rg int i = 1; i <= n; ++i) scanf("%lf", s + i), s[i] += s[i - 1];
    for (rg int i = 1; i <= n; ++i) A[i] = (db) s[i] + i - L - 1;
    for (rg int i = 1; i <= n; ++i) B[i] = (db) s[i] + i;
    for (rg int i = 1; i <= n; ++i) {
        while (hd < tl && slope(Q[hd], Q[hd + 1]) < 2 * A[i]) ++hd;
        dp[i] = dp[Q[hd]] + (A[i] - B[Q[hd]]) * (A[i] - B[Q[hd]]);
        while (hd < tl && slope(Q[tl - 1], Q[tl]) > slope(Q[tl - 1], i)) --tl;
        Q[++tl] = i;
    }
    printf("%lld\n", (long long) dp[n]);
    return 0;
}

完结撒花 \(qwq\)

「HNOI2008」玩具装箱

原文：https://www.cnblogs.com/zsbzsb/p/11746551.html