[CSP-S 2019] 划分

GitHub 跳转原题关系图返回列表

用单调队列维护每个前缀的最优上一段结尾，贪心取尽量靠后的可行断点。

OJ: luogu

题目 ID: P5665

难度:提高+/省选-

标签:动态规划贪心单调队列前缀和

日期: 2026-07-06 08:46

题意

给定正整数序列 a[1..n]，要把它划分成若干个连续段，要求每一段的段和非递减。设各段段和为：

text

1s1 <= s2 <= ... <= sk

目标是最小化：

text

1s1^2 + s2^2 + ... + sk^2

type=0 时直接给出所有 a_i；type=1 时按题面给出的递推和区间参数生成数据。

思路

小数据可以做动态规划：枚举最后一段从哪里开始，再检查它的段和是否不小于上一段。

cpp

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// brute.cpp：小数据动态规划，枚举最后一段起点，要求段和非递减。
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);

int n, type_id_input;
long long a[105], prefix_sum[105];
long long dp[105][105]; // dp[i][j]：前 i 个数，最后一段从 j+1 到 i

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

    cin >> n >> type_id_input;
    if (type_id_input == 0) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
    } else {
        // 对拍生成器只生成 type=0。这里保留读取入口，避免格式不完整。
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = INF;
        }
    }

    for (int i = 1; i <= n; i++) {
        long long sum = prefix_sum[i];
        dp[i][0] = sum * sum;
    }

    for (int i = 1; i <= n; i++) {
        for (int last = 1; last < i; last++) {
            long long last_sum = prefix_sum[i] - prefix_sum[last];
            for (int prev = 0; prev < last; prev++) {
                if (dp[last][prev] == INF) {
                    continue;
                }
                long long prev_sum = prefix_sum[last] - prefix_sum[prev];
                if (prev_sum <= last_sum) {
                    dp[i][last] = min(dp[i][last], dp[last][prev] + last_sum * last_sum);
                }
            }
        }
    }

    long long answer = INF;
    for (int j = 0; j < n; j++) {
        answer = min(answer, dp[n][j]);
    }
    cout << answer << '\n';
    return 0;
}

满分做法的关键观察是：所有 a_i 都是正数。对于固定前缀 i，如果最后一段越短，它的平方贡献越小；因此在满足“上一段段和不超过最后一段段和”的前提下，我们希望最后一段尽量短，也就是上一段结尾尽量靠后。

令：

text

1
2c[i] = a[1] + a[2] + ... + a[i]
g[i] = 前缀 i 的最优上一段结尾

最后一段是 (g[i]+1)..i，段和为：

text

1c[i] - c[g[i]]

为了让它接在 g[i] 的最优划分后面，需要满足：

text

1c[g[i]] - c[g[g[i]]] <= c[i] - c[g[i]]

移项得到：

text

12*c[g[i]] - c[g[g[i]]] <= c[i]

也就是说，每个候选断点 t 有一个关键值：

text

1key(t) = 2*c[t] - c[g[t]]

当 key(t) <= c[i] 时，t 可以作为前缀 i 的上一段结尾。我们要选满足条件且尽量靠后的 t。

扫描 i=1..n 时，c[i] 单调递增；同时可以证明最优候选的 key 也适合用单调队列维护。队头给出当前可行且最靠后的断点，队尾则维护候选 key 的单调性。

算出所有 g[i] 后，从 n 沿着 g[n]、g[g[n]] 往前跳，就得到最优划分的所有段，累加段和平方即可。答案可能超过 long long，代码用 __int128 输出。

代码

cpp

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98// main.cpp：线性贪心。g[i] 表示处理到 i 时，最后一段从 g[i]+1 开始最优。
#include <bits/stdc++.h>
using namespace std;

const long long MOD_GEN = 1LL << 30;

int n, type_id_input;
vector<long long> prefix_sum;
vector<int> pre_pos, q;

void print_int128(__int128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    if (x < 0) {
        cout << '-';
        x = -x;
    }
    string s;
    while (x > 0) {
        s.push_back((char)('0' + x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

long long key_value(int idx) {
    return 2 * prefix_sum[idx] - prefix_sum[pre_pos[idx]];
}

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

    cin >> n >> type_id_input;
    prefix_sum.assign(n + 1, 0);
    pre_pos.assign(n + 1, 0);
    q.assign(n + 2, 0);

    if (type_id_input == 0) {
        for (int i = 1; i <= n; i++) {
            long long a;
            cin >> a;
            prefix_sum[i] = prefix_sum[i - 1] + a;
        }
    } else {
        long long x, y, z, b1, b2;
        int m;
        cin >> x >> y >> z >> b1 >> b2 >> m;
        vector<long long> b(n + 1, 0);
        b[1] = b1;
        b[2] = b2;
        for (int i = 3; i <= n; i++) {
            b[i] = (x * b[i - 1] + y * b[i - 2] + z) % MOD_GEN;
        }

        int last_p = 0;
        for (int i = 1; i <= m; i++) {
            int p;
            long long l, r;
            cin >> p >> l >> r;
            for (int j = last_p + 1; j <= p; j++) {
                long long a = b[j] % (r - l + 1) + l;
                prefix_sum[j] = prefix_sum[j - 1] + a;
            }
            last_p = p;
        }
    }

    int head = 1;
    int tail = 1;
    q[1] = 0;

    for (int i = 1; i <= n; i++) {
        while (head < tail && key_value(q[head + 1]) <= prefix_sum[i]) {
            head++;
        }
        pre_pos[i] = q[head];
        while (head < tail && key_value(i) <= key_value(q[tail])) {
            tail--;
        }
        q[++tail] = i;
    }

    __int128 answer = 0;
    int pos = n;
    while (pos > 0) {
        __int128 sum = prefix_sum[pos] - prefix_sum[pre_pos[pos]];
        answer += sum * sum;
        pos = pre_pos[pos];
    }

    print_int128(answer);
    cout << '\n';
    return 0;
}

复杂度

每个位置最多进出单调队列一次，时间复杂度 $O(n)$ 。

空间复杂度为 $O(n)$ ，需要保存前缀和、前驱位置和队列。

总结

本题表面是划分 DP，核心优化来自正数序列的贪心性质：最后一段在可行时应尽量短。把可行条件整理成 key(t) <= c[i] 后，就可以用单调队列在线维护最优断点。

P5665 [CSP-S 2019] 划分

题目描述

2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $n$ 组数据，数据从 $1 \sim n$ 编号， $i$ 号数据的规模为 $a_i$ 。

小明对该题设计出了一个暴力程序，对于一组规模为 $u$ 的数据，该程序的运行时间为 $u^2$ 。然而这个程序运行完一组规模为 $u$ 的数据之后，它将在任何一组规模小于 $u$ 的数据上运行错误。样例中的 $a_i$ 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点 $1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n$ ，使得

\sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum_{i=k_p+1}^{n} a_i

注意 $p$ 可以为 $0$ 且此时 $k_0 = 0$ ，也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化：

\left(\sum_{i=1}^{k_1} a_i\right)^2 + \left(\sum_{i=k_1+1}^{k_2} a_i\right)^2 + \cdots + \left(\sum_{i=k_p+1}^{n} a_i\right)^2

小明觉得这个问题非常有趣，并向你请教：给定 $n$ 和 $a_i$ ，请你求出最优划分方案下，小明的程序的最小运行时间。

输入格式

由于本题的数据范围较大，部分测试点的 $a_i$ 将在程序内生成。

第一行两个整数 $n, type$ 。 $n$ 的意义见题目描述， $type$ 表示输入方式。

若 $type = 0$ ，则该测试点的 $a_i$ 直接给出。输入文件接下来：第二行 $n$ 个以空格分隔的整数 $a_i$ ，表示每组数据的规模。
若 $type = 1$ ，则该测试点的 $a_i$ 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 $x, y, z, b_1, b_2, m$ 。接下来 $m$ 行中，第 $i (1 \leq i \leq m)$ 行包含三个以空格分隔的正整数 $p_i, l_i, r_i$ 。

对于 $type = 1$ 的 $23 \sim 25$ 号测试点， $a_i$ 的生成方式如下：

给定整数 $x, y, z, b_1, b_2, m$ ，以及 $m$ 个三元组 $(p_i, l_i, r_i)$ 。

保证 $n \geq 2$ 。若 $n \gt 2$ ，则 $\forall 3 \leq i \leq n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \bmod 2^{30}$ 。

保证 $1 \leq p_i \leq n, p_m = n$ 。令 $p_0 = 0$ ，则 $p_i$ 还满足 $\forall 0 \leq i \lt m$ 有 $p_i \lt p_{i+1}$ 。

对于所有 $1 \leq j \leq m$ ，若下标值 $i (1 \leq i \leq n)$ 满足 $p_{j−1} \lt i \leq p_j$ ，则有

a_i = \left(b_i \bmod \left( r_j − l_j + 1 \right) \right) + l_j

上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

text

1
25 0
5 1 7 9 9

输出 #1

text

输入输出样例 #2

输入 #2

text

1
210 0
5 6 7 7 4 6 2 13 19 9

输出 #2

text

输入输出样例 #3

输入 #3

text

1
2
3
4
510000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234

输出 #3

text

14972194419293431240859891640

说明/提示

【样例 1 解释】

最优的划分方案为 $\{5,1\}, \{7\}, \{9\}, \{9\}$ 。由 $5 + 1 \leq 7 \leq 9 \leq 9$ 知该方案合法。

答案为 $(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247$ 。

虽然划分方案 $\{5\}, \{1\}, \{7\}, \{9\}, \{9\}$ 对应的运行时间比 $247$ 小，但它不是一组合法方案，因为 $5 \gt 1$ 。

虽然划分方案 $\{5\}, \{1,7\}, \{9\}, \{9\}$ 合法，但该方案对应的运行时间为 $251$ ，比 $247$ 大。

【样例 2 解释】

最优的划分方案为 $\{5\}, \{6\}, \{7\}, \{7\}, \{4,6,2\}, \{13\}, \{19,9\}$ 。

【数据范围】

::cute-table[]{tuack}

测试点编号	$n \leq$	$a_i \leq$	$type =$
$1 \sim 3$	$10$	$10$	$0$
$4 \sim 6$	$50$	$10^3$	^
$7 \sim 9$	$400$	$10^4$	^
$10 \sim 16$	$5000$	$10^5$	^
$17 \sim 22$	$5 \times 10^5$	$10^6$	^
$23 \sim 25$	$4 \times 10^7$	$10^9$	$1$

对于 $type=0$ 的所有测试点，保证最后输出的答案 $\leq 4 \times 10^{18}$ 。

所有测试点满足： $type \in \{0,1\}$ ， $2 \leq n \leq 4 \times 10^7$ ， $1 \leq a_i \leq 10^9$ ， $1 \leq m \leq 10^5$ ， $1 \leq l_i \leq r_i \leq 10^9$ ， $0 \leq x,y,z,b_1,b_2 \lt 2^{30}$ 。

[CSP-S 2019] 划分

目录

题意

思路

代码

复杂度

总结