Skip to content

洛谷 - P4744 [Wind Festival] Iron Man

题解约 1.3 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

[Midnight - 23:59]

在风筝节上交到了老铁(并不是 Nishikino),接触了 OI,gyx 全身的热情都被点燃啦!!为了更好地参与到下一届风筝节的工作中去,gyx 准备开始为期一年的学习。

#题目描述

gyx 想用全部的时间学(tui)OI(fei)!!!

gyx 为了合理的利用所有时间学 OI,他开始规划自己的学习计划。

首先,gyx 的眼里每年有 nn 天,因为 gyx 实在是太想学习啦,所以他并没有留下玩耍的时间(每天都全部用来学 OI 或者文化课),gyx 划分天数的原则是,在每一天中,gyx 对 OI 的感兴趣程度相同。但是,未免 gyx 也会因生活琐事而没法静心学习,所以某些天 gyx 对 OI 的兴趣程度有可能是负的。

然后,gyx 开始安排学习 OI 的时间,gyx 统计出他要学习的 OI 知识有 kk 种。因为 gyxgyx 是一个追求完美的人,他认为对于每一种 OI 知识,知识体系的完整性是必要的,某一个部分的 OI 知识学习过程中一旦停下来会影响自己的学习效果,所以他会用连续的一些天来学习一个部分的知识,期间不能停下来学习文化课,也不会穿插着进行几种知识的学习。

但是注意,gyx 在进行每部 OI 知识的学习之间可以留出一些时间段用来学文化课。并且,gyx 并不介意各个部分 OI 知识间学习的顺序,因为他对每一部分的 OI 知识兴趣程度是相同的。

现在,gyx 想知道他总共用于学 OI 的日子兴趣值之和是多少,因为 gyx 还没有学习过高级的规划算法,所以 gyx 将他学习计划的规划交给你,你可以选择任意一个小于等于 nn 的一个正整数 ii,使他从第 ii 天开始,进行长 nn 天的学习(不一定一开始就必须学 OI),但在这一年中他一定要把清单中所有的知识都学完,gyx 相信你一定能给出兴趣值之和最高的方法。

#输入格式

两个正整数 n,kn, k,分别代表 gyx 眼中一年有 nn 天,gyxgyx 要学习的知识有 kk 种。

接下来一行有 nn 个整数,第 ii 个数 aia_i 代表 gyxgyxii 天对 OI 的兴趣程度。

#输出格式

输出一个整数,代表他总共学 OI 的所有日子兴趣值之和最大是多少。

#输入输出样例

样例输入 #1

6 2
2 -4 3 -1 2 3

样例输出 #1

10

样例解释 #1

从第 33 个时间段开始学习,那么他学 OI 的这一年兴趣程度的序列便为:

3,1,2,3,2,43, -1, 2, 3, 2, -4

用于学习两个知识的时间段分别是新序列的第11个和第3,4,53,4,5个,则答案为 3+(2+3+2)=103 + (2 + 3 + 2) = 10

#数据范围与约定

  • 对于 10%10\% 的数据,满足 k=1k = 1
  • 对于另 30%30\% 的数据,满足 k=2k = 2
  • 对于 100%100\% 的数据,满足:1k501 \le k \le 50kn105k \le n \le 10^5ai104|a_i| \le 10^4

#思路

BZOJ2288 生日礼物 的加强版。

原题的选择条件是选择「至多 kk 个」,而本题是选择「恰好 kk 个」,同时本题多出了环形的条件。

环形的处理:如果开头和结尾的值符号相同,合并即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <algorithm>
#include <cmath>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, k, p = 1, a[N], pre[N], nxt[N], ans;
bool vis[N];
std::priority_queue<std::pair<int, int>> q;
std::vector<int> nums;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> k;

for (int i = 1, x; i <= n; i++) {
cin >> x;

if (static_cast<long long>(a[p]) * x < 0) {
a[++p] = x;
} else {
a[p] += x;
}

nums.emplace_back(x);
}

std::sort(nums.begin(), nums.end(), std::greater<>());

if (nums[0] < 0) {
for (int i = 0; i < k; i++) {
ans += nums[i];
}

cout << ans << endl;

exit(0);
}

if (a[1] > 0 && a[p] > 0) {
a[1] += a[p--];
}

int cnt = 0;
for (int i = 1; i <= p; i++) {
pre[i] = i == 1 ? p : i - 1;
nxt[i] = i == p ? 1 : i + 1;

if (a[i] > 0) {
ans += a[i];
cnt++;
a[i] = -a[i];
}

q.emplace(a[i], i);
}

while (cnt > k) {
int i = q.top().second;
q.pop();

if (vis[i]) continue;

cnt--;
ans += a[i];

int l = pre[i],
r = nxt[i];

a[i] = a[l] + a[r] - a[i];

pre[i] = pre[l];
nxt[pre[l]] = i;
vis[l] = true;

pre[nxt[r]] = i;
nxt[i] = nxt[r];
vis[r] = true;

q.emplace(a[i], i);
}

cout << ans << endl;

return 0;
}