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

[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 くんは，自分が最終的に取るピースの大きさの合計を最大化したい．

N/A

N/A

### 課題 ケーキのピースの数 $ 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 \- - - - - -