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

· · 题解

思路

首先我们把公式展开来看：

\sum_{i=1}^{k} i \times s_i = \sum_{i=1}^{k} i \times \sum_{j=r_{i-1}+1}^{r_i} a_j

我们把求和顺序调换一下，可以发现每个元素 a_j 的贡献取决于它所在的段编号，也就是被乘上的系数是多少。也就是说，每个元素 a_j 的系数等于它所属段的编号。

那么我们要做的事情就是：如何给每个元素分配段编号，使得整体加权和最大。

我们从右往左考虑，当我们从右往左切割时，每多切一刀就会让右边一段的系数增加 1。因此，如果一个“后缀的和”是正的，那把它放到右边能增加整体和；反之，如果后缀和是负的，就不想让它被更高的系数乘上，即不想让它太靠右。

于是问题转化成了我们需要知道每个后缀的和，并选择最大的几个后缀加到结果里。

具体而言，我们定义后缀和数组 \text{suf}[i] = a_i + a_{i+1} + \dots + a_n 并且令 \text{suf}[n+1] = 0。显然，\text{suf}[1] 就是整段的总和，也就是 k=1 的答案。当我们增加一个分段时，相当于把一个“后缀”独立出来乘以更大的系数。那我们就应该选择最大的后缀和来提升整体值。所以我们把所有后缀和（除了第一个）按从大到小排序。然后依次累加，得到每个 k 的答案，这样就能得到所有的 v_1, v_2, \dots, v_n。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int n,a[N],suf[N];
signed main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        memset(suf,0,sizeof suf);
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
        sort(suf+2,suf+n+1,greater<int>());int v=suf[1];
        for(int i=1;i<=n;i++)cout<<v<<" ",v+=(i<n)*suf[i+1];
        cout<<"\n";
    }
    return 0;
}