ケーキの切り分け２ (Cake 2)

# 「JOI 2014/2015 决赛」分蛋糕 2 **译自 [JOI 2014/2015 决赛](https://www.ioi-jp.org/joi/2014/2015-ho/index.html) T2「[ケーキの切り分け２](https://www.ioi-jp.org/joi/2014/2015-ho/2015-ho.pdf)」** ## 题目描述 JOI 君和 IOI 酱是双胞胎兄妹。 JOI 君最近闲暇时常常会做甜点。今天 JOI 君也烤了蛋糕吃，IOI 酱立马嗅到了蛋糕的香气于是跑来想分着吃。 蛋糕是圆形的，从蛋糕中某点开始将蛋糕放射状切为 $ N $ 块，按逆时针顺序编号为 $ 1 $ 到 $ N $ 。也就是说，对任意 $ i $ 来说 $ (1 \leq i \leq N) $ ，第 $ i $ 块蛋糕紧挨着第 $ i-1 $ 块与第 $ i+1 $ 块（不过第 $ 0 $ 块相当于第 $ N $ 块，第 $ N+1 $ 块相当于第 $ 1 $ 块）。第 $ i $ 块蛋糕的大小为 $ A_i $ 。由于切蛋糕的人刀功很不好，所以 $ A_i $ 互不相同。  JOI 君和 IOI 酱按照以下的方法分这 $N$ 块蛋糕： 1. 首先 JOI 君从这 $ N $ 块蛋糕中任选一块取走； 2. 然后，从 IOI 酱开始， IOI 酱和 JOI 君交替地从剩下的蛋糕中选出一块取走。不过，当且仅当一块蛋糕两旁的蛋糕至少有一块已经被选择，这块蛋糕才能被选择。如果可供选择的蛋糕有多个， IOI 酱会选择最大的一个，而 JOI 君可以任选一个。 JOI 君想让自己所得到的蛋糕大小的合计值最大。 #### 任务 给出蛋糕的块数 $ N $ 和这 $ N $ 块蛋糕的大小。请编写程序求出 JOI 君得到的蛋糕大小的总和的最大值。 ## 输入格式 第一行为整数 $ N $ ，表示蛋糕被切成了 $ N $ 块； 接下来 $ N $ 行中的第 $ i $ 行 $ (1 \leq i \leq N) $ 为一个整数 $ A_i $ 。表示第 $ i $ 块蛋糕的大小。 ## 输出格式 输出一行： JOI 君得到的蛋糕大小的总和的最大值。 ## 样例 #### 输入样例 1 ```plain 5 2 8 1 10 9 ``` #### 输出样例 1 ```plain 18 ``` #### 样例说明 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 $。 #### 输入样例 2 ```plain 8 1 10 4 5 6 2 9 3 ``` #### 输出样例 2 ```plain 26 ``` #### 输入样例 3 ```plain 15 182243672 10074562 977552215 122668426 685444213 3784162 463324752 560071245 134465220 21447865 654556327 183481051 20041805 405079805 564327789 ``` #### 输出样例 3 ```plain 3600242976 ``` ## 数据范围 对于 $ 15\% $ 的分值： - $ N \leq 20 $ 对于另 $45\%$ 的分值： - $ N \leq 300 $ 对于 $100\%$ 的分值，所有输入数据满足以下条件： - $ 1 \leq N \leq 2000 $； - $ 1 \leq A_i \leq 10^9 $； - 每个 $ A_i $ 都不同。 感谢@ミク 提供的翻译

[problemUrl]: https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_b JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので $ 2 $ 人でケーキを分けることになった． ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを $ N $ 個のピースに切り分け，ピースに $ 1 $ から $ N $ まで反時計回りに番号をつけた．つまり，$ 1\ \leqq\ i\ \leqq\ N $ に対し，$ i $ 番目のピースは $ i\ -\ 1 $ 番目と $ i\ +\ 1 $ 番目のピースと隣接している (ただし $ 0 $ 番目は $ N $ 番目，$ N\ +\ 1 $ 番目は $ 1 $ 番目とみなす)．$ i $ 番目のピースの大きさは $ A_i $ だったが，切り方がとても下手だったので $ A_i $ はすべて異なる値になった． 図 1: ケーキの例 ($ N\ =\ 5 $，$ A_1\ =\ 2 $，$ A_2\ =\ 8 $，$ A_3\ =\ 1 $，$ A_4\ =\ 10 $，$ A_5\ =\ 9 $) この $ N $ 個を JOI くんと IOI ちゃんで分けることにした．分け方は次のようにすることにした： 1. まず JOI くんが $ N $ 個のうちの好きな $ 1 $ つを選んで取る． 2. その後，IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを $ 1 $ つずつ取っていく．ただし，両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず，取れるピースが複数あるときは，IOI ちゃんはそのうち最も大きいものを選んで取り，JOI くんはそのうちで好きなものを選んで取ることができる． JOI くんは，自分が最終的に取るピースの大きさの合計を最大化したい．

標準入力から以下の入力を読み込め． - $ 1 $ 行目には整数 $ N $ が書かれており，ケーキが $ N $ 個のピースに切り分けられていることを表す． - 続く $ N $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には整数 $ A_i $ が書かれており，$ i $ 番目のピースの大きさが $ A_i $ であることを表す．

標準出力に，JOI くんが取れるピースの大きさの合計の最大値を表す整数を $ 1 $ 行で出力せよ． - - - - - -

5
2
8
1
10
9

18

8
1
10
4
5
6
2
9
3

26

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

3600242976

### 課題 ケーキのピースの数 $ N $ と，$ N $ 個のピースの大きさの情報が与えられたとき，JOI くんが取れるピースの大きさの合計の最大値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ N\ \leqq\ 2\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ 1\,000\,000\,000 $． - $ A_i $ はすべて異なる． ### 小課題 #### 小課題 1 \[15 点\] - $ N\ \leqq\ 20 $ を満たす． #### 小課題 2 \[45 点\] - $ N\ \leqq\ 300 $ を満たす． #### 小課題 3 \[40 点\] 追加の制限はない． - - - - - - ### Sample Explanation 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 $ となる． - - - - - - ### Sample Explanation 2 \- - - - - -