a316. TOI 2019/04 潛力組：獎金關卡

題目描述

一排 N 個按鈕各有一個正整數積分。按下仍有效的按鈕可得到它的積分，同時讓左右相鄰的按鈕失效。按下失效的按鈕不會得分，但仍會讓相鄰按鈕失效。每個按鈕的積分最多領取一次。你可以自行決定按哪些按鈕以及順序，求可獲得的最大總積分。

輸入格式

第一行是 N，第二行是 N 個按鈕積分。

• 3 ≤ N ≤ 1000000
• 每個積分為 1 到 99 的整數。

輸出格式

輸出最大總積分。

來源

TOI 2019 年 4 月潛力組〈獎金關卡〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201904/A2-Bonus(Q).pdf 題意核對：M_SQRT 所保存之原題 PDF。