102187: [AtCoder]ABC218 H - Red and Blue Lamps
Description
Score : $600$ points
Problem Statement
There are $N$ lamps numbered $1$ through $N$ arranged in a row. You are going to light $R$ of them in red and $N-R$ in blue.
For each $i=1,\ldots,N-1$, a reward of $A_i$ is given if Lamp $i$ and Lamp $i+1$ light up in different colors.
Find the maximum total reward that can be obtained by efficiently deciding the colors of the lamps.
Constraints
- $2 \leq N \leq 2\times 10^5$
- $1 \leq R \leq N-1$
- $1 \leq A_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $R$
$A_1$ $A_2$ $\ldots$ $A_{N-1}$
Output
Print the answer.
Sample Input 1
6 2 3 1 4 1 5
Sample Output 1
11
Lighting up Lamps $3, 5$ in red and Lamps $1, 2, 4, 6$ in blue yields a total reward of $A_2+A_3+A_4+A_5=11$.
You cannot get any more, so the answer is $11$.
Sample Input 2
7 6 2 7 1 8 2 8
Sample Output 2
10
Lighting up Lamps $1, 2, 3, 4, 5, 7$ in red and Lamp $6$ in blue yields a total reward of $A_5+A_6=10$.
Sample Input 3
11 7 12345 678 90123 45678901 234567 89012 3456 78901 23456 7890
Sample Output 3
46207983
Input
题意翻译
## 题意翻译 现在你有 $N$ 盏灯排成一列，编号为 $1$ 到 $N$。对于任意一盏灯，你可以将其变成红色或蓝色。你想让其中的 $R$ 盏灯变成红色，$N-R$ 盏灯变成蓝色。 当第 $i$ 和 $i+1$ 盏灯以不同的颜色发光时，你将获得 $A_i$ 点报酬。 请你计算当有 $R$ 盏灯为红色，$N-R$ 盏灯为蓝色时，你所获得的报酬和的最大值。Output
分数：$600$分
问题描述
有一排编号为$1$到$N$的$N$盏灯。你需要将其中的$R$盏灯点亮为红色，其余的灯点亮为蓝色。
对于每$i=1,\ldots,N-1$，如果灯$i$和灯$i+1$点亮的颜色不同，将会获得奖励$A_i$。
通过高效地决定灯的颜色，找出可以获得的最大总奖励。
约束条件
- $2 \leq N \leq 2\times 10^5$
- $1 \leq R \leq N-1$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都是整数。
输入
从标准输入中按照以下格式获取输入：
$N$ $R$
$A_1$ $A_2$ $\ldots$ $A_{N-1}$
输出
打印答案。
样例输入1
6 2 3 1 4 1 5
样例输出1
11
将灯$3, 5$点亮为红色，将灯$1, 2, 4, 6$点亮为蓝色，可以获得总奖励$A_2+A_3+A_4+A_5=11$。
你无法获得更多的奖励，所以答案是$11$。
样例输入2
7 6 2 7 1 8 2 8
样例输出2
10
将灯$1, 2, 3, 4, 5, 7$点亮为红色，将灯$6$点亮为蓝色，可以获得总奖励$A_5+A_6=10$。
样例输入3
11 7 12345 678 90123 45678901 234567 89012 3456 78901 23456 7890
样例输出3
46207983