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 代表 gyxgyx 第 ii 天对 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\% 的数据，满足：1≤k≤501 \le k \le 50，k≤n≤105k \le n \le 10^5，∣ai∣≤104|a_i| \le 10^4。

#思路

BZOJ2288 生日礼物 的加强版。

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

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

#代码

C++
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;
}