题目背景

本题是 My rating is ... 的 hard 版本。注意题目限制与 easy 版本不同。

题目描述下方有简化题意。

My rating is 1064.（被 2 - Tower 炸掉了，因此现在打不开了）

题目描述

小 A 想在 Codeforces 上发 $n$ 篇帖子！例如：

“My rating is 1064.”

“I am PolarSea.”

“你知道 phi 吗？你知道你的 phi 处是哪里吗？你知道它的 price 吗？1e9 + 7。”

“每道题都很简单，全场虐题不用烦。T1 到场先签到，T2 上手随便切，T3 一交就能过，T4 稍想也能 A。DP 转移很容易，数学结论尽皆知。建图方法极明显，数据结构很一般。不卡空间不卡常，码量不大手不酸。没有毒瘤大模拟，只有良多大水题。片刻四题提交过，人人 AK 笑开颜。”

“……”

为此，小 A 新注册了 $k$ 个账号。他决定按照顺序发出每篇帖子，并用到所有 $k$ 个账号。不过刷屏过多会引起 Mike 的注意并被封号，小 A 当然不希望这样：他进行了一些评估，得到了每篇帖子的安全指数 $a_i$，表示他发出第 $i$ 篇帖子后不被封号的概率。

由于第一印象非常重要，小 A 定义一个账号的安全指数为该账号所发出的第一篇帖子的安全指数。此外，如果用同一个账号连续发出两个帖子，该账号的安全指数会减小这两篇帖子安全指数的较小值。

小 A 希望找到这样一个发帖方案，使得所有账号的安全指数之和最大。你只需要求出安全指数之和的最大值即可。

---

「简化题意」

将 $1\sim n$ 不重不漏地分进恰好 $k$ 个集合 $S_1,S_2,\cdots,S_k$ 中 且 $|S_i|>0$。记 $i$ 被分入第 $d_i$ 个集合，求

$$\left(\sum_{i=1}^k a[{\min_{j\in S_i}j}]\right)-\left(\sum_{i=1}^{n-1}\min(a_i,a_{i+1})[d_i=d_{i+1}]\right) $$

的最大值，其中左边的 $[x]$ 表示下标为 $x$，右边的 $[x]$ 表示当 $x$ 成立时取值为 $1$，当 $x$ 不成立时取值为 $0$。

输入格式

本题有多组数据。

第一行一个整数 $t$，表示该测试点编号。
第二行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个帖子的安全指数。

输出格式

对于每组数据，一行一个整数表示答案。

0
3
4 2
1 1 3 2
8 3
1 3 2 8 6 4 7 5
40 10
9843011 22841896 42690334 3412396 8420789 100693326 23390709 11537210 145661796 21418321 16914724 146120903 14287416 9157773 259599687 16469809 13371424 221660485 23554750 3004543 19382066 514113557 959488450 162305801 377127750 240963428 597774302 18789772 647693870 517468301 547221960 162988230 309004668 267293109 867629494 476230153 70400563 100943563 140708197 999999999

3
13
5882440256

提示

「样例 1 说明」

小 A 可以使用账号 $1$ 发帖子 $1,2$ 和 $4$，用账号 $2$ 发帖子 $3$。其安全程度为 $(a_{\min(1,2,4)}-\min(a_1,a_2))+a_3=1-1+3=3$。

「数据范围与约定」

本题共有 6 个测试点。

• Testcase #0（1 point）：是样例。
• Testcase #1（20 points）：$k=2$。
• Testcase #2（20 points）：$n\leq 10$，$k\leq 4$。
• Testcase #3（15 points）：$k=3$。
• Testcase #4（20 points）：$n\leq 10^3$。
• Testcase #5（24 points）：无特殊限制。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^5$，$0 \leq a_i \leq 10^9$，$T=10$（除 Testcase #0）。
对于所有测试点，时间限制 1s，空间限制 128MB。

「题目来源」

Sweet Round 07 B2。
idea & solution：tzc_wk & Alex_Wei（加强）；data：Alex_Wei；验题：chenxia25。

My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. ……

Upvote -77 Downvote                  PolarSea