| 题目名称 | 3477. [BZOJ 2288]生日礼物 |
|---|---|
| 输入输出 | present.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 gao
于2020-09-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：2， 通过率：0% | ||||
 Theresis |
10 | 0.042 s | 4.37 MiB | C++ |
|
Theresis |
10 | 3.194 s | 11.96 MiB | C++ |
| 本题关联比赛 | |||
| EYOI常规赛 7th | |||
| EYOI常规赛 7th | |||
| 关于 生日礼物 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
小根堆贪心鲨我
Theresis
2020-09-21 20:04
1楼
| ||||
【题目描述】
翰翰 18 岁生日的时候，达达给她看了一个神奇的序列 a[1 ∼ n]。她被允许从中选择不超过 m个子段作为自己的生日礼物。翰翰想要知道选择元素之和的最大值。你能帮助她吗？
【输入格式】
第一行包含两个整数 n, m。
第二行包含 n 个整数 a1, a2, · · · , an。
【输出格式】
输出一个整数，表示答案。
【样例输入】
5 2 2 -3 2 -1 2
【样例输出】
5
【提示】
选择子段 {2}, {2, −1, 2} 是最优的，选择的元素之和为 5
【数据范围与约定】
1 ≤ n, m ≤ 10^5, −10^4 ≤ ai ≤ 10^4。
【来源】
《算法竞赛进阶指南》