自动搬运

查看原文

来自洛谷，原作者为

	lkjzyd20 Am I Sunshine Deprimere? I think so.

搬运于2025-08-24 23:12:36，当前版本为作者最后更新于2025-04-10 15:46:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$ 和正整数 $k$。需要将整个数组划分成 $k$ 个非空子序列，使得每个元素只属于一个子序列。每个子序列的“价值”计算公式为

其中 $j_1, j_2, \dots, j_l$ 是该子序列中所选元素在原数组中的下标，$m$ 表示该元素在子序列中的位置。最终我们的目标是使所有 $k$ 个子序列价值的和最大。

思路

对于一个子序列，其价值不仅与选择了哪些元素有关，同时也与这些元素在子序列中所处的位置有关。由于位置随位置从 $1$ 到 $l$ 递增，我们更希望大的值获得更大的位置。设每个子序列中让价值最大的那个元素在原数组中的下标分别为 $i_1, i_2, \dots, i_k$。可以证明，总存在一种调整方法，使得：

• 在 $k$ 个子序列中，将最靠右（即下标最大的那个）的子序列保持不变，这个子序列的贡献为 $a_x + x$（假设 $x = \max\{i_1, i_2, \dots, i_k\}$）。
• 其他 $k-1$ 个子序列，我们都将让使价值最大的元素放在序列的最前面，这样它们的位置都是 $1$，贡献就是各自的 $a_{i}$ 加上 $1$。

因为 $k-1$ 是固定的常数，我们可以把问题简化为：

对于每个可能的 $x$（表示最靠右的选中元素位置），如何在 $x$ 前面（即区间 $[1, x-1]$）选择 $k-1$ 个元素，使它们的和最大？

我们枚举 $x$ 从 $k$ 到 $n$ 保证了每个可能成为最靠右的极大元素都被考虑，最后得到的最大值就是全局最优答案。答案就可以表示为所有 $x$ 中的最大值：$x+a_x+sum_x$，其中 $sum_x$ 是第 $x$ 个元素左侧的 $k−1$ 个最大元素的和，用小根堆维护即可。

代码

#include<bits/stdc++.h>
#define int long long 
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=5000010;
int n,k;
int a[N],tot,ans;
priority_queue<int,vector<int>,greater<int> > q;
main(){
	cin>>n>>k;
	rep(i,1,n)cin>>a[i];
	rep(i,1,k-1)q.push(a[i]),tot+=a[i];
	ans=max(ans,k+a[k]+tot);
	rep(i,k+1,n){
		if(!q.empty()){
			if(q.top()<a[i-1])tot-=q.top(),q.pop(),tot+=a[i-1],q.push(a[i-1]); 
		}
		ans=max(ans,i+a[i]+tot);
	}
	cout<<ans; 
	return 0;
}