题解：洛谷 P14242 [CCPC 2024 Shandong I] 分割序列

洛谷 P14242 [CCPC 2024 Shandong I] 分割序列 题解（贪心）

题意

给定长度为 \(n\) 的整数序列 \(a_1, a_2, \cdots, a_n\)，将序列分成 \(k\) 段连续且非空的子数组，使得序列中的每个元素恰属于一个子数组。令 \(s_i\) 表示从左到右第 \(i\) 个子数组里的元素之和，对于每个 \(1 \le k \le n\)，求下式的最大值。

\[\sum\limits_{i = 1}^k i \times s_i \]

数据范围与约定

\(1 \le n \le 5 \times 10^5\)；

\(-10^6 \le a_i \le 10^6\)；

保证所有数据 \(n\) 之和不超过 \(5 \times 10^5\)。

题解

在下文中，我们称 \(\sum\limits_{i = 1}^k i \times s_i\) 这个式子，即题面中要求的式子，成为“权值和”。

考虑基本情况。

对于一个长度为 \(n\) 的数组 \(a\)，在 \(a_k\) 和 \(a_{k + 1}\) 之间拆分开，前面的权值和为 \(\sum \limits _{i = 1} ^{k} a_i\)，后面的权值和为 \(\sum \limits _{i = k + 1} ^{n} a_i\)，整个数组的权值和 \(S\) 为：

\[\begin{align*}S &= (\sum \limits _{i = 1} ^{k} a_i) + 2 \cdot (\sum \limits _{i = k + 1} ^{n} a_i) \\&= (\sum \limits _{i = 1} ^{k} a_i) + (\sum \limits _{i = k + 1} ^{n} a_i) + (\sum \limits _{i = k + 1} ^{n} a_i) \\&= (\sum \limits _{i = 1} ^{n} a_i) + (\sum \limits _{i = k + 1} ^{n} a_i)\end{align*} \]

其实 \(\sum \limits _{i = k + 1} ^{n} a_i\) 就是 \(a\) 的后缀和。

对于分成 \(3\) 段，会发现其权值和就是分成 \(2\) 段时的权值和再加上一段后缀和。

所以我们得出结论，对于一个长度为 \(n\) 的数组 \(a\)，将其分成 \(k\) 段，所得出的权值和为 \(\operatorname{S}(k) = \operatorname{S}(k - 1) + \operatorname{suf}\)，其中 \(\operatorname{suf}\) 为后缀和。

出于贪心的思想，想要让权值和最大，\(\operatorname{suf}\) 就需要最大（因为 \(\operatorname{S}(k)\) 一定）。

CODE

#include<bits/stdc++.h>
using namespace std;
/*====================*/
using lnt = long long;
/*====================*/
#define endl "\n"
/*====================*/
const int N = 5e5 + 10;
/*====================*/
int arr[N];
/*====================*/
lnt suf[N];
/*====================*/
void Solve()
{int n; cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i]; suf[n + 1] = 0;for (int i = n; i >= 1; i--){suf[i] = suf[i + 1] + arr[i];}lnt sum = suf[1];cout << sum << " ";sort(suf + 2, suf + n + 1, greater<lnt>());for (int i = 2; i <= n; i++){sum += suf[i];cout << sum << " ";}cout << endl;
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int t = 1; cin >> t;while (t--) Solve();return 0;
}