#2709. 「BalticOI 2015」黑客

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

题目译自 BalticOI 2015 Day2 Hacker(HAC),原题面见附加文件。
如欲转载翻译,请注明翻译者信息及转载出处。

黑客 Byteasar 获得了参加今年 IHO,即国际黑客奥林匹克竞赛(International Hacker Olympiad)的机会。比赛的一个任务是与一个系统操作者对抗。有 nnn 台从 111nnn 编号的计算机,连接成了一个环,即编号为 iii 的计算机与编号为 i+1i+1i+1 的计算机相连(对于 i=1,2,3,⋯ ,n−1i=1,2,3,\cdots,n-1i=1,2,3,,n1),编号为 nnn 的计算机与编号为 111 的计算机相连。 这场比赛以一个系统操作者与黑客的游戏进行。

  • Byteasar 先操作,之后,系统操作者和 Byteasar 交替操作;
  • 第一次操作时,Byteasar 可以选择任一计算机然后黑掉它(例如,找寻一些操作系统的漏洞);
  • 第一次操作时,操作者可以选择任一没有被黑的电脑,然后保护它(例如,安装最新的安全更新);
  • 在所有接下来的操作中,Byteasar 要么什么都不做 (a),要么选择既没有被黑也没有被保护,同时和被黑的电脑直接相连的电脑(b),然后黑掉它;
  • 在所有接下来的操作中,操作者要么什么都不做(a),要么选择既没有被黑也没有被保护,同时和被保护的电脑直接相连的电脑(b),然后保护它;
  • 当双方在相邻的两个操作中都选择什么都不做,这个游戏结束。

在游戏开始,没有电脑被黑,也没有电脑被保护。

每台电脑都有一个特定的价值 viv_ivi,表示存储在其中的数据的价值。对于每一个被黑的电脑 iii,Byteasar 获得它的价值 viv_ivi 分。Byteasar 是一个十分出色的黑客,但是他不会算法。这就是他请你写一个程序去计算他的最大可能得分的原因。假设系统操作者永远采用最佳策略。

输入格式

输入的第一行包含一个正整数 nnn,表示计算机台数。第二行是一个 nnn 个正整数的序列 viv_iviviv_ivi 表示计算机 iii 上存储的数据价值。

输出格式

一行一个整数,表示 Byteasar 获得的最大可能得分。

样例

样例输入 1

4
7 6 8 4

样例输出 1

13

样例说明

第一个样例中,Byteasar 第一个黑掉的电脑是 222 号(获得 666 分)。作为回应,系统操作者会保护电脑 333。在接下来的操作中,Byteasar 会黑点电脑 111(获得 777 分)。最后,操作者会保护电脑 444

样例输入/输出 2

详见附加文件 hac_sample2.in/ans

数据范围与提示

本题采用子任务式测评,只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务,n≥2,1≤vi≤2×103n\ge 2,1\le v_i\le 2\times 10^3n2,1vi2×103

对于每个子任务满足的条件如下:

子任务 条件 分数
111 n≤300n\le 300n300 202020
222 n≤5×103n\le 5\times 10^3n5×103 202020
333 n≤5×105n\le 5\times 10^5n5×105,且第一次操作中,Byteasar 黑掉电脑 111 是最优的。 202020
444 n≤5×105n\le 5\times 10^5n5×105 404040