题解：P12076 [OOI 2025] Cute Subsequences

lkjzyd20 · 2025-04-10 15:46:44 · 题解

简要题意

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

\max_{1\le m \le l} (a_{j_m} + m)

其中 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;
}