形式化题目

给定正整数序列 $C_1,\ldots,C_N$ 与常数 $L$。把下标 $1\ldots N$ 划分成若干连续段，每段 $i\ldots j$（$i \leqslant j$）装入一个容器：

• 该段容器长度必须不小于 $x = (j-i) + \sum_{k=i}^{j} C_k$（即段内玩具之间放 $j-i$ 个单位填充物）；
• 长度为 $x$ 的容器制作费用为 $(x-L)^2$；
• 容器数目与长度不受限制，超过 $L$ 也可以。

各段费用相加，求运走全部玩具的最小总费用。

样例 $N=5,\ L=4,\ C=[3,4,2,1,4]$ 的一种最优划分如下，总费用为 $1$：

注意单件一段没有填充物（$j-i=0$），所以 $\{1\}$ 的长度是 $3$ 而不是 $4$；费用对每段独立计算后求和，不能把整段总长度代入一次公式。

正解

思路

第一步：分段 DP。 设 $S[i]=\sum_{k=1}^{i}C_k$（$S[0]=0$），$dp[i]$ 为前 $i$ 件玩具的最小费用，$dp[0]=0$。若最后一段是 $j{+}1\ldots i$，该段长度为

引入 $T[i] = S[i] + i$，则 $x = T[i] - T[j] - 1$，转移为

初始 $dp[0]=0$，遍历顺序就是 $i$ 从 $1$ 扫到 $N$，答案为 $dp[N]$。

对样例逐个 $i$ 枚举所有 $j$ 取最小，得到下表（$x_i = T[i]-1-L$ 是第三步要用的查询点，每个 $i$ 标出取到最小值的 $j$）：

要观察两点：$dp$ 本身不单调（$dp[4]=1 < dp[3]=5$），所以不能贪心地固定上一个断点；但最优 $j$ 序列 $0,1,2,2,4$ 单调不减，这说明「哪个 $j$ 最优」随 $i$ 只会右移，有优化空间。朴素实现对每个 $i$ 扫一遍 $j$，$O(N^2)$ 在 $N=5\times10^4$ 时约 $2.5\times10^9$ 次运算，必然超时。

第二步：把转移展开成直线族。 固定 $i$ 令 $x_i = T[i]-1-L$（只与 $i$ 有关），转移中随 $j$ 变化的部分是

也就是说每个 $j$ 对应一条直线 $\ell_j:\ y = m_jx + b_j$，而 $dp[i] = \min_j \ell_j(x_i) + x_i^2$。求 $\min$ 只需要在直线族上查询。样例的直线族如下：

验证 $i=3$（$x_3=7$）：$\ell_0(7)=0$、$\ell_1(7)=-39$、$\ell_2(7)=-44$，最小 $-44$，加 $x_3^2=49$ 得 $dp[3]=5$，与 DP 表一致。

第三步：双单调 ⇒ 单调队列。 由 $C_i \geqslant 1$ 知 $T$ 严格递增，于是：

• 斜率单调：$m_j = -2T[j]$ 随 $j$ 严格递减；
• 查询单调：$x_i = T[i]-1-L$ 随 $i$ 严格递增。

斜率与查询同向单调时，直线族的下凸壳可以用双端队列维护，每次查询只弹队首、每次插入只弹队尾：

1. 队首（查询时）：若 value(front) >= value(second) 就弹出队首。斜率递减的两条线只相交一次，首线在当前查询点被追平后，对一切更大的 $x$ 只会更差，可以永久丢弃——这就是 DP 表里「最优 $j$ 单调右移」的队列实现。
2. 队尾（插入时）：若 $\ell_a$ 与 $\ell_c$ 的交点 $x_{ac}$ 不晚于 $\ell_a$ 与队尾 $\ell_b$ 的交点 $x_{ab}$，则 $\ell_b$ 在任何查询点都取不到最小值，弹出 $\ell_b$。交点 $x_{ab} = \dfrac{b_b-b_a}{m_a-m_b}$ 的分母同号，交叉相乘即可用整数精确比较，避免浮点误差。

每条直线进出队列各一次，均摊 $O(1)$。样例中 $i=5$、$x_5=14$ 连续越过交点 $x_{23}\approx11.17$、$x_{34}=12$，把 $\ell_2,\ell_3$ 依次弹出，只剩 $\ell_4$，算得 $dp[5] = -195 + 14^2 = 1$，即最终答案。

代码

下面的 min_cost() 就是上述单调队列：hull 存直线 $(m,b)$，value() 算直线在查询点的取值，is_shadow() 用交叉相乘判断队尾死线，t 即 $T[i]$。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:43
# update_at: 2026-09-30 21:43

import sys
from collections import deque

Line = tuple[int, int]  # (斜率, 截距)：直线 y = m*x + b，公共的 x² 项统一后加


def value(line: Line, x: int) -> int:
    """直线在 x 处的取值（不含公共的 x²）。"""
    m, b = line
    return m * x + b


def is_shadow(a: Line, b: Line, c: Line) -> bool:
    """b 是否被 a、c 夹成死线：交点不前移，b 永远取不到最小值。"""
    (ma, ba), (mb, bb), (mc, bc) = a, b, c
    # 交点横坐标 (b_i - b_j) / (m_j - m_i)，斜率严格递减使分母同号，交叉相乘避免浮点
    return (bb - ba) * (mb - mc) >= (bc - bb) * (ma - mb)


def min_cost(costs: list[int], limit: int) -> int:
    """斜率优化 + 单调队列：依次推出 dp[i]，返回最后一件玩具装完的最小费用。"""
    hull: deque[Line] = deque()
    hull.append((0, 0))  # j = 0：前 0 件玩具 T=0、dp=0 对应的直线
    t = 0                # T[i] = 前缀和 S[i] + i，随 i 严格递增
    dp = 0

    for c in costs:
        t += c + 1                          # 每件玩具让前缀和与下标各 +1
        x = t - 1 - limit                   # 以 j 分段时容器长度 = x - T[j]
        while len(hull) > 1 and value(hull[0], x) >= value(hull[1], x):
            hull.popleft()                  # x 随 i 递增：被追平的首线以后只会更差
        m, b = hull[0]
        dp = m * x + b + x * x              # dp[i] = min_j 直线值 + x²
        new = (-2 * t, dp + t * t)          # dp[i] + (x - T[i])² 展开后的 (m, b)
        while len(hull) > 1 and is_shadow(hull[-2], hull[-1], new):
            hull.pop()                      # 维护下凸壳：交点左移的尾线整段多余
        hull.append(new)

    return dp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, limit = next(data), next(data)
    costs = [next(data) for _ in range(n)]
    print(min_cost(costs, limit))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:45
 * update_at: 2026-10-05 12:45
 */
// 斜率优化 DP：转移展开成直线族 y = -2*T[j]*x + (dp[j]+T[j]^2)，
// 斜率与查询点双单调，用单调队列维护下凸壳，O(N) 求最小装箱费用。

#include <iostream>
using namespace std;

typedef long long ll;
typedef __int128 lll; // 凸壳比较的中间乘积可达 1e35，64 位整数会溢出

const int MAXN = 50005;

int n;
ll limit;
ll T[MAXN];  // T[i] = 前缀和 S[i] + i，由 C[i] >= 1 知其严格递增
ll dp[MAXN]; // dp[i] 表示前 i 件玩具的最小装箱费用
int q[MAXN]; // 单调队列：存直线对应的下标 j，斜率 -2*T[j] 随下标严格递减

// 第 j 条直线：y = -2*T[j] * x + (dp[j] + T[j]^2)，公共的 x^2 项统一后加
lll line_value(int j, ll x) {
    return (lll)(-2 * T[j]) * x + (lll)dp[j] + (lll)T[j] * T[j];
}

// 队首 a 在当前查询点已不优于 b：两条直线只有一个交点，追平后 a 永远更差
bool is_worse_front(int a, int b, ll x) {
    return line_value(a, x) >= line_value(b, x);
}

// b 被 a、c 夹成死线：交点 x_ab >= x_bc 时 b 取不到最小值，交叉相乘避免浮点
bool is_shadow(int a, int b, int c) {
    lll ya = (lll)dp[a] + (lll)T[a] * T[a];
    lll yb = (lll)dp[b] + (lll)T[b] * T[b];
    lll yc = (lll)dp[c] + (lll)T[c] * T[c];
    return (yb - ya) * (T[c] - T[b]) >= (yc - yb) * (T[b] - T[a]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> limit;
    for (int i = 1; i <= n; i++) {
        ll c;
        cin >> c;
        T[i] = T[i - 1] + c + 1; // 前缀和与下标各加 1
    }

    int head = 1, tail = 1;
    q[1] = 0; // j = 0：前 0 件玩具，T[0] = dp[0] = 0

    for (int i = 1; i <= n; i++) {
        ll x = T[i] - 1 - limit; // 断点为 j 时容器长度 = x - T[j]
        while (head < tail && is_worse_front(q[head], q[head + 1], x)) {
            head++; // x 随 i 递增，被追平的队首以后只会更差
        }
        int j = q[head];
        ll len = x - T[j]; // 该段容器长度与 limit 的差
        dp[i] = dp[j] + len * len; // 最优段的差恰为 dp[i]-dp[j]，不会溢出

        while (head < tail && is_shadow(q[tail - 1], q[tail], i)) {
            tail--; // 维护下凸壳：交点左移的尾线永远取不到最小值
        }
        q[++tail] = i;
    }

    cout << dp[n] << '\n';
    return 0;
}

复杂度

• 时间 $O(N)$：每件玩具只做常数次队首、队尾比较，每个下标入队一次、出队一次。
• 空间 $O(N)$：$C$ 数组与直线队列（队列摊还长度远小于 $N$）。
• 与标准 C++ 斜率优化解法同阶；Python 侧无溢出风险（int 任意精度，最大答案 $21837422283$ 也远小于 $2^{63}$，但段长上界对应费用可达 $2.5\times10^{23}$）。

总结

• 先建模：$dp[i] = \min_j \{dp[j] + (T[i]-T[j]-1-L)^2\}$，其中 $T[i]=S[i]+i$ 把「前缀和 + 下标」合并成一个严格递增的量。
• 再变形：转移对 $j$ 展开成 $\ell_j(x_i) + x_i^2$，把「枚举段首」变成「在直线族上取最小值」。
• 最后利用 $T$ 严格递增带来的斜率、查询双单调，用单调队列维护下凸壳，$O(N)$ 求出最小费用。
• 易错点：填充物是「件数 $-1$ 个」；费用按段独立求和；$L$ 只是费用参考点，段长可以小于 $L$。
• 边界：$N=1$ 时队列里只有初始直线 $\ell_0$，$dp[1] = (C_1-L)^2$；$T$ 严格递增保证斜率、查询都严格单调，无需退化分支。