No.45 回転寿司
yuki2006問題文最終更新日: 2022-12-06 17:18:36
問題文
あなたは、回転寿司にきている。
お寿司は$N$皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさが\(V_i\)で表される。
流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、
2連続で皿を取ることが出来ない。
もちろん、自分の前を過ぎたお寿司も取ることが出来ない。
この時、あなたが得られる美味しさの最大の合計値を求めてください。
お寿司は一周回ってくることはないとする。
入力
\(N \) \(V_1\,V_2\,V_3 \ldots V_N \)
1行目に、お寿司の数\(N (1\le N \le 1000)\)が与えられます。
2行目に、お寿司の美味しさ \( V_i (1\le V_i \le 100,1 \le i \le N) \)が半角スペース区切りで与えれます。
出力
あなたが得られる美味しさの最大の合計値を求めてください。
サンプル
サンプル1
入力
4 1 2 3 4
出力
6
お寿司の取り方は、「1個目と３個目」のお寿司を取る、「１個目と４個目」のお寿司を取る、「２個目と4個目」のお寿司を取る方法などがあるが、
２個目、４個目のお寿司を取ることで、最大の美味しさが得られる。
サンプル2
入力
4 5 4 4 9
出力
14
1個目のお寿司と4個目のお寿司を取ることで最大の美味しさの合計が得られる。
サンプル3
入力
7 1 2 9 10 1 1 4
出力
16
2,10,4と取れば最大の16が得られる。
10の後の2つをあえてスルーしないといけない。
サンプル4
入力
1 100
出力
100
1皿しかない場合もあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。