P12076 [OOI 2025] Cute Subsequences
题目背景
试题来源。
题目描述
给定一个长度为
n
n
n 的正整数数组
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \\ldots, a_n
a1,a2,…,an，以及一个正整数
k
k
k。你需要将该数组划分为
k
k
k 个非空子序列，使得每个元素恰好属于一个子序列。
子序列指的是从原始序列中删除若干个元素（可以为零），但不改变剩余元素的相对顺序后所得到的序列。
设第
i
i
i 个子序列包含的是原数组中下标为
j
1
<
…
<
j
l
j_1 < \\ldots < j_l
j1<…<jl 的元素。该子序列的「价值」定义为
max
1
≤
m
≤
l
(
a
j
m
+
m
)
\\max\\limits_{1 \\le m \\le l}(a_{j_m} + m)
1≤m≤lmax(ajm+m)。
将数组划分为
k
k
k 个子序列的「代价」是这
k
k
k 个子序列的价值之和。
请你计算出数组在划分方案最优时所能获得的最大代价。
输入格式
第一行包含两个正整数
n
n
n 和
k
k
k（
1
≤
k
≤
n
≤
500
000
1 \\le k \\le n \\le 500\\,000
1≤k≤n≤500000）—— 分别表示数组的长度以及要划分出的子序列数量。
第二行包含
n
n
n 个正整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \\ldots, a_n
a1,a2,…,an（
1
≤
a
i
≤
10
9
1 \\le a_i \\le 10^9
1≤ai≤109）—— 表示数组中的元素。
输出格式
输出一个整数，表示将给定数组划分为
k
k
k 个非空子序列所能获得的最大代价。
输入输出样例 #1
输入 #1
5 3
3 7 10 1 2
输出 #1
24
说明/提示
样例解释
在样例中，可以将数组划分为
[
3
,
10
]
[3, 10]
[3,10]、
[
7
]
[7]
[7]、
[
1
,
2
]
[1, 2]
[1,2]。那么答案为：
(
10
+
2
)
+
(
7
+
1
)
+
(
2
+
2
)
=
12
+
8
+
4
=
24.
(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24.
(10+2)+(7+1)+(2+2)=12+8+4=24.
本题的测试点共包含六个分组。只有当某个分组的所有测试点以及其依赖的所有分组测试点均通过时，才能获得该分组的分数。
| 0 | 0 | – | – | – | 样例测试点。 |
| 1 | 14 |
n ≤ 8 n \\le 8 n≤8 |
– | 0 | |
| 2 | 19 | – |
k = 2 k = 2 k=2 |
– | |
| 3 | 17 | – | – | – | 满足
a i + 1 ≤ a i a_{i+1} \\le a_i ai+1≤ai。 |
| 4 | 21 | – | – | – | 满足
a i + 1 ≥ a i − 1 a_{i+1} \\ge a_i – 1 ai+1≥ai−1。 |
| 5 | 15 |
n ≤ 1000 n \\le 1000 n≤1000 |
– | 0, 1 | |
| 6 | 14 | – | – | 0 – 5 |
C++实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rd read()
#define pc(a) putchar(a)
#define enter putchar('\\n')
#define fo(a,b,c) for(int a = (b); a <= (c); ++a)
#define of(a,b,c) for(int a = (b); a >= (c); —a)
#define pii pair<int,int>
#define pb push_back
#define endl '\\n'
const int N = 5e5+7, M = 2e5+7, INF=0x3f3f3f3f;
inline int read() {
int x=0,f=1; char ch = getchar();
while (ch<'0' || ch>'9') {if (ch == '-')f=–1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch–'0';ch=getchar();}
return x*f;
}
int n, k;
int a[N];
void Input() {
n = rd; k = rd;
fo (i, 1, n) a[i] = rd;
}
signed main() {
Input();
priority_queue<ll,vector<ll>,greater<ll>> pq;
ll sum = 0, ans=–1;
fo (i, 1, n) {
if (i >= k) ans = max(ans, a[i]+i+sum);
if (pq.size() < k–1) {
pq.push(a[i]);
sum += a[i];
} else if (!pq.empty() && a[i] > pq.top()) {
sum -= pq.top();
pq.pop();
sum += a[i];
pq.push(a[i]);
}
}
printf("%lld", ans);
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
