形式化题目

给定非负整数序列 $C_1, C_2, \dots, C_N$ 和常数 $M$。要把这 $N$ 个数按原顺序切成若干个连续段，一段 $C_{l} \dots C_{r}$ 的费用为该段和的平方加上 $M$，即

求一种切分方式，使所有段的费用之和最小，输出这个最小值。多组数据，读到文件末尾为止。

正解

思路

第一步：分段 DP。 设 $dp_i$ 表示打印前 $i$ 个单词的最小费用，$S_i = C_1 + C_2 + \dots + C_i$ 为前缀和。枚举最后一段的起点 $j$（即前 $j$ 个单词已归入前面的段，第 $j+1 \dots i$ 个单词单独成一段）：

这有 $O(N^2)$ 个候选转移，$N \leqslant 5 \times 10^5$ 时无法接受，必须优化。

第二步：把「选来源」变成「选直线」。 展开平方项并整理：

把每个决策 $j$ 看成平面上的点 $P_j = (S_j,\ dp_j + S_j^2)$，那么 $dp_i$ 就是：用斜率为 $2S_i$ 的直线去扫这些点，取最小截距，再减去 $S_i^2$ 加上 $M$。

第三步：两个单调性引出单调队列。 最小截距只会在这个点集的下凸壳上取到。而本题恰好有两个天然的单调性：

1. $C_i$ 非负 $\Rightarrow$ $x_j = S_j$ 随 $j$ 递增，点按 $j$ 从小到大依次产生，天然按 $x$ 排好序；
2. $S_i$ 递增 $\Rightarrow$ 询问斜率 $k_i = 2S_i$ 只增不减。

于是用单调队列维护下凸壳：

• 队头弹出：若队头相邻两点的斜率 $\leqslant k_i$，说明切点已经在更右边，队头以后永远不会再优，弹出；
• 队尾弹出：新点 $P_i$ 入队前，若 $\text{slope}(q_{tail-2}, q_{tail-1}) \geqslant \text{slope}(q_{tail-2}, P_i)$，则 $q_{tail-1}$ 落在上凸的位置上，不可能再成为任何询问的最小截距点，弹出。

每个下标至多进出队列一次，转移总复杂度 $O(N)$。

斜率怎么比？ 全部用交叉相乘：$\dfrac{y_b - y_a}{x_b - x_a} \leqslant k$ 改写成 $y_b - y_a \leqslant k \cdot (x_b - x_a)$。$S_j \leqslant 5\times10^5 \times 10^3 = 5\times 10^8$（按题面权值上限估计），$dp \leqslant 10^{10}$ 量级，乘积会到 $10^{20}$——Python 的整数无所谓，C++ 需要注意 long long。

一个坑：$C_i = 0$。 此时会出现 $S_i = S_j$，即 $x$ 相同的重复点。由于 $dp$ 非降，新点的 $y = dp_i + S_i^2$ 必不小于旧点的 $y$，新点完全被旧点覆盖——直接不入队即可。这样队列内 $x$ 严格递增，队头、队尾的比较都不会出现除零（我们用乘法比较，本来也不会除零，但 $x$ 相同的点留在队列里会让凸壳判断出错）。

边界：$N = 0$。 一个单词都不用打印，费用为 $0$。

样例推演（$N=5,\ M=5$，$C = 5\ 9\ 5\ 7\ 5$，$S = 0,5,14,19,26,31$）：

注意 $i=3$ 时下标 $1$ 被队尾弹出、$i=5$ 时下标 $3$ 被队尾弹出——它们已经不可能再成为最优决策，这正是凸壳在收缩。最终 $dp_5 = 230$，与样例输出一致。

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71#!/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 22:10
# update_at: 2026-09-30 22:10

import sys

# 凸包点 j 的纵坐标：dp[j] + S[j]^2（横坐标是 S[j]，斜率优化推式子里移项得到）
def y_of(dp: list[int], S: list[int], j: int) -> int:
    """直线截距式 y(j) = dp[j] + S[j]²，凸包上点 j 的 y 值。"""
    return dp[j] + S[j] * S[j]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:  # 多组数据，读到 EOF
        try:
            n = next(data)
        except StopIteration:
            break
        m = next(data)

        if n == 0:  # 没有单词，不用打印，费用为 0
            out.append('0')
            continue

        S = [0] * (n + 1)  # S[i] = 前 i 个单词的权值和
        s = 0
        for i in range(1, n + 1):
            s += next(data)
            S[i] = s

        dp = [0] * (n + 1)  # dp[i]：前 i 个单词分段的最小费用
        q = [0] * (n + 1)   # 凸包队列，存下标，X 坐标 S[j] 严格递增
        head, tail = 0, 1   # 队列有效区间 [head, tail)

        for i in range(1, n + 1):
            k = 2 * S[i]  # 当前决策直线的斜率，随 i 单调不减 → 可从队头淘汰

            # 队头两点斜率 <= k 时，队头不可能再成为最优决策
            while tail - head >= 2 and \
                    (y_of(dp, S, q[head + 1]) - y_of(dp, S, q[head])) <= \
                    k * (S[q[head + 1]] - S[q[head]]):
                head += 1

            j = q[head]
            d = S[i] - S[j]
            dp[i] = dp[j] + d * d + m

            # 新点加入队尾前，先弹出使凸包失去"斜率严格递增"的点
            while tail - head >= 2 and \
                    (y_of(dp, S, q[tail - 1]) - y_of(dp, S, q[tail - 2])) * (S[i] - S[q[tail - 2]]) >= \
                    (y_of(dp, S, i) - y_of(dp, S, q[tail - 2])) * (S[q[tail - 1]] - S[q[tail - 2]]):
                tail -= 1

            if S[i] > S[q[tail - 1]]:
                q[tail] = i
                tail += 1
            # S[i] == S[q[-1]] 时 dp 非降 ⇒ 新点 y 更大，被旧点完全覆盖，不入队

        out.append(str(dp[n]))

    print('\n'.join(out))


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
75
76
77
78/**
 * 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:55
 * update_at: 2026-10-05 12:55
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 500005;

// 注意值域：N <= 5*10^5，C 为非负权值，前缀和、dp 均在 ll 范围内
ll C[MAXN];  // 每个单词的权值
ll S[MAXN];  // S[i] = 前 i 个单词的权值和
ll dp[MAXN]; // dp[i]：前 i 个单词分段打印的最小费用
int q[MAXN]; // 单调队列：保存凸壳上的决策下标，x 坐标 S[j] 严格递增
int head, tail; // 队列有效区间 [head, tail)

// 凸壳上点 j 的纵坐标：由转移式移项得到 y(j) = dp[j] + S[j]^2
inline ll y_of(int j) {
    return dp[j] + S[j] * S[j];
}

int main() {
    int n;
    ll m;
    // 多组数据，读到文件末尾为止
    while (scanf("%d %lld", &n, &m) == 2) {
        if (n == 0) { // 一个单词都不用打印，费用为 0
            printf("0\n");
            continue;
        }

        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &C[i]);
            S[i] = S[i - 1] + C[i];
        }

        // 决策下标 0（一个单词都不选）先入队
        head = 1; tail = 1;
        q[tail++] = 0;

        for (int i = 1; i <= n; ++i) {
            ll k = 2 * S[i]; // 当前决策直线的斜率，随 i 单调不减

            // 队头：相邻两点斜率 <= k 时，队头不再可能是最优决策，弹出
            while (tail - head >= 2 &&
                   (y_of(q[head + 1]) - y_of(q[head])) <= k * (S[q[head + 1]] - S[q[head]])) {
                ++head;
            }

            // 队头即最优决策
            int j = q[head];
            ll d = S[i] - S[j];
            dp[i] = dp[j] + d * d + m;

            // 队尾：弹出破坏下凸壳（斜率不严格递增）的点
            // 斜率比较全部用交叉相乘，避免除法和除零
            while (tail - head >= 2 &&
                   (y_of(q[tail - 1]) - y_of(q[tail - 2])) * (S[i] - S[q[tail - 2]]) >=
                   (y_of(i) - y_of(q[tail - 2])) * (S[q[tail - 1]] - S[q[tail - 2]])) {
                --tail;
            }

            // C_i = 0 会导致 S[i] = S[q[tail-1]]（x 重复）：
            // 此时 dp 非降，新点 y 更大，被旧点完全覆盖，直接不入队
            if (S[i] > S[q[tail - 1]]) {
                q[tail++] = i;
            }
        }

        printf("%lld\n", dp[n]);
    }
    return 0;
}

复杂度

每组数据：队列中每个下标至多入队、出队各一次，队头/队尾操作均摊 $O(1)$，总时间 $O(N)$；空间 $O(N)$（前缀和、dp、队列各一个数组）。

图示解析

凸壳与切点：为什么队头就是最优决策

下图展示样例推演到 $i = 5$（询问斜率 $k_5 = 2S_5 = 62$）时，队列中的点构成的下凸壳（示意图，纵轴 $y = dp_j + S_j^2$）：

1
2
3
4
5
6
7 y
 │                       ● P4(26, 876)      ← 队头即切点：slope(P3,P4)≈52.7 ≤ 62 ≤ slope(P4,P5)=63
 │                  ● P3(19, 507)
 │        ● P2(14, 312)
 │   ● P0(0, 0)
 └──────────────────────────────────── x = S[j]
        P0      P2      P3     P4    P5(31,1191)

读图要点：

• 询问直线是一族斜率为 $2S_i$ 的平行线，从下往上平移，第一个碰到的点就是最小截距点（切点）；
• 切点左侧相邻边的斜率一定 $\leqslant k$、右侧相邻边的斜率一定 $> k$；$k$ 只增，所以切点只会右移，被淘汰的队头不必保留；
• 队尾弹出的对象是「上凸点」：如 $P_1(5, 55)$ 在 $P_0$ 与 $P_2$ 连线上方，任何直线扫到 $P_1$ 时都先碰到 $P_0$ 或 $P_2$，它永远不优。

总结

• 本题是斜率优化的入门经典：平方代价分段 DP + 决策单调。
• 推导套路：把 $\min$ 里的 $(S_i - S_j)^2$ 展开，将转移改写成「定斜率直线扫点取最小截距」；$x$、斜率两个单调性成立时，用单调队列维护下凸壳即可 $O(N)$。
• 实现要点：斜率比较用交叉相乘防溢出/防除零；$C_i = 0$ 导致的 $x$ 重复点不入队；$N = 0$ 输出 $0$；多组数据逐组重建。