P7874 「SWTR-7」My rating is -32（easy version）
题目背景
#### 本题是 My rating is ... 的 easy 版本。注意题目限制和数据范围与 [hard](https://www.luogu.com.cn/problem/T167832) 版本不同。
#### 请注意特殊的时空限制，题目描述下方有简化题意。
[My rating is -32.](https://codeforces.com/blog/entry/71123)
说明：上方的帖子是机房里某个同学很久很久以前的黑历史，现在成了机房传世经典，不是为了出比赛才发的，请不要误会。
题目描述
小 A 想在 Codeforces 上发 $n$ 篇帖子！例如：
> “My rating is 1064.”
>
> “I am PolarSea.”
>
> “你知道 phi 吗？你知道你的 phi 处是哪里吗？你知道它的 price 吗？1e9 + 7。”
>
>“每道题都很简单，全场虐题不用烦。T1 到场先签到，T2 上手随便切，T3 一交就能过，T4 稍想也能 A。DP 转移很容易，数学结论尽皆知。建图方法极明显，数据结构很一般。不卡空间不卡常，码量不大手不酸。没有毒瘤大模拟，只有良多大水题。片刻四题提交过，人人 AK 笑开颜。”
>
> “……”
为此，小 A 新注册了 $k$ 个账号。他决定**按照从 $1$ 到 $n$ 的顺序**发出每篇帖子，并**用到所有 $k$ 个账号**。不过刷屏过多会引起 Mike 的注意并被封号，小 A 当然不希望这样：他进行了一些评估，得到了每篇帖子的安全指数 $a_i$，表示他发出第 $i$ 篇帖子后不被封号的概率。
由于第一印象非常重要，小 A 定义一个账号的安全指数为该账号所发出的**第一篇**帖子的安全指数。此外，如果**用同一个账号连续发出两个帖子**，Mike 会立刻封掉这个账号，因此这种情况**是不合法的**。
小 A 希望找到这样一个发帖方案，使得所有账号的安全指数之和最大。你只需要求出安全指数之和的最大值即可。
---
**「简化题意」**
将 $1\sim n$ **不重不漏**地分进 $k$ 个集合 $S_1,S_2,\cdots,S_k$ 中，满足**相邻的数不在同一集合** 且 $|S_i|>0$。求
$$\sum_{i=1}^k a[{\min_{j\in S_i}j}]$$
的最大值，其中 $[]$ 表示**下标**。
输入格式
无
输出格式
无
说明/提示
**「样例 1 说明」**
小 A 只能使用账号 $1$ 发帖子 $1$ 和 $3$，剩下的帖子用账号 $2$ 发。其安全程度为 $a_{\min(1,3)}+a_{\min(2,4)}=2$。
**「数据范围与约定」**
本题共有 6 个测试点。
- Testcase #0（1 points）：是样例。
- Testcase #1（10 points）：$k=2$。
- Testcase #2（30 points）：$n\leq 10$，$k\leq 4$。
- Testcase #3（15 points）：$k=3$。
- Testcase #4（20 points）：$n\leq 64$，$k\leq 7$。
- Testcase #5（24 points）：无特殊限制。
对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^4$，$0 \leq a_i \leq 10^9$，$T=10$。
对于所有测试点，**时间限制 200ms，空间限制 16MB。**
**「题目来源」**
[Sweet Round 07](https://www.luogu.com.cn/contest/) B1。
idea & solution：[tzc_wk](https://www.luogu.com.cn/user/115194)；data & 验题：[Alex_Wei](https://www.luogu.com.cn/user/123294)。
> **My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. ……**
>
> **Upvote -43 Downvote PolarSea**