← 返回题目列表

AtCoder · abc456_f

F. 计划假期

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

高桥正在努力决定他的日程 N 天。最初,没有一天是假期。

他可以重复以下任一操作任意次数:

  • 选择一个整数 i 之间 1 和 N,包含在内,并让日子 i 放假。此操作成本 A_i.
  • 选择一个整数 i 之间 2 和 N-1,包含在内,这样两天 i-1 和日 i+1 已经是假期了,让一天 i 放假。此操作是免费的。

找出创建连续块所需的最小总成本 K 或更多假期。

T 给出了测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。
  • 总和 N 所有测试用例最多 2\times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里, \mathrm{case}_i 表示输入 i- 第一个测试用例。每个测试用例均按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

3
5 2
3 1 4 1 5
6 4
24 3 22 39 4 29
15 7
220651272 302798780 874479994 657822311 613294668 479624013 241168404 610547619 762548286 256160531 823041612 951553052 226556081 649525901 153805947

示例输出 1

2
29
1902064780

对于第一个测试用例,可以通过执行以下操作来创建至少两个假期的连续块:

  • 创造一天 2 节假日使用第一种操作方式。这需要花费 1.
  • 创造一天 4 节假日使用第一种操作方式。这需要花费 1.
  • 创造一天 3 节假日使用第二种操作方式。这是免费的。

这一系列操作的总成本是 2。不可能以低于以下的成本创建两个或多个假期的连续块 2,所以输出 2.