P15817 [JOI 2015 Final] 分蛋糕 2 / Cake 2
题目描述
JOI 君和 IOI 酱是双胞胎兄妹。JOI 君最近沉迷于制作点心，今天他又烤了一个蛋糕准备自己吃，但蛋糕刚出炉时，IOI 酱闻着香味就来了，于是两人决定分享这个蛋糕。
蛋糕是圆形的。从某一点开始沿放射状切出切口，将蛋糕切成了 $N$ 块，并按逆时针方向给这些块依次编号为 $1$ 到 $N$。也就是说，对于 $1 \le i \le N$，第 $i$ 块与第 $i-1$ 块和第 $i+1$ 块相邻（这里认为第 $0$ 块是第 $N$ 块，第 $N+1$ 块是第 $1$ 块）。第 $i$ 块的大小是 $A_i$，但由于切蛋糕的技术很差，所有的 $A_i$ 值都互不相同。
:::align{center}
图 1: 蛋糕示例 ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 9$)
:::
他们决定按以下规则来分配这 $N$ 块蛋糕：
1. 首先，由 JOI 君从 $N$ 块中任意选择一块取走。
2. 然后，从 IOI 酱开始，IOI 酱和 JOI 君轮流从剩余的块中每次取走一块。但是，只能取走**至少有一侧相邻的块已经被取走**的块。当有多个块可以取时，IOI 酱必须选择其中**最大**的一块取走，而 JOI 君可以选择其中任意一块取走。
JOI 君希望最大化他自己最终取到的所有块的大小之和。
### 任务
给定蛋糕的块数 $N$ 以及 $N$ 块蛋糕的大小信息，请编写一个程序，计算 JOI 君能取到的块的大小之和的最大值。
输入格式
从标准输入读取以下输入。
* 第一行包含一个整数 $N$，表示蛋糕被切成了 $N$ 块。
* 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $A_i$，表示第 $i$ 块蛋糕的大小为 $A_i$。
输出格式
向标准输出输出一行，包含一个整数，表示 JOI 君能取到的块的大小之和的最大值。
说明/提示
### 样例解释 1
JOI 君按以下方式取蛋糕是最优的：
1. JOI 君取走第 2 块。这块的大小是 $8$。
2. IOI 酱取走第 1 块。这块的大小是 $2$。
3. JOI 君取走第 5 块。这块的大小是 $9$。
4. IOI 酱取走第 4 块。这块的大小是 $10$。
5. JOI 君取走第 3 块。这块的大小是 $1$。
最终，JOI 君取到的块的大小之和为 $8 + 9 + 1 = 18$。
### 数据范围
所有输入数据满足以下条件：
* $1 \le N \le 2000$。
* $1 \le A_i \le 1000000000$。
* 所有的 $A_i$ 互不相同。
### 子任务
#### 子任务 1 [15 分]
* 满足 $N \le 20$。
#### 子任务 2 [45 分]
* 满足 $N \le 300$。
#### 子任务 3 [40 分]
没有额外限制。
翻译由 DeepSeek V3.2 完成