题解：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

CPP

#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;
}

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

文章操作

思路

Code

相关推荐

评论

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