#P1002. 能量站
时间限制2000 ms
内存限制512 MiB
通过率—0 / 0 次提交
CSP-J 2026 预测模拟卷。原创训练，非官方试题。
时间限制：2.0 s 内存限制：512 MiB 分值：100 分
题目描述
一条公路上有 n 个能量站，第 i 个能量站提供 a_i 单位能量。小 P 可以选择若干个能量站，但任意两个被选择的能量站不能相邻，并且最多只能选择 k 个。
求能够获得的最大总能量。
输入格式
第一行 n,k。 第二行 n 个正整数 a_1,...,a_n。
输出格式
输出一个整数，表示最大总能量。
输入输出样例 #1
6 2
3 7 2 9 1 5
16
输入输出样例 #2
7 3
5 1 6 10 2 8 4
23
数据范围
1 ≤ n ≤ 2×10^5；1 ≤ k ≤ min(100,n)；1 ≤ a_i ≤ 10^9。答案需使用 64 位整数。
测试点
| 测试点 | 规模 | 特殊性质 | 分值 |
|---|---|---|---|
| 1-2 | n≤10 | 无 | 10 |
| 3-4 | n≤20 | ||
| 5-6 | n≤100 | k=1 | |
| 7-8 | 所有 a_i=1 | ||
| 9-10 | n≤10^3 | k≤10 | |
| 11-12 | n≤10^4 | k=1 | |
| 13-14 | k≤100 | ||
| 15-16 | n≤10^5 | k≤50 | |
| 17-20 | n≤2×10^5 | k≤100 | 20 |
