No.45 Conveyor Belt Sushi
タグ : / 解いたユーザー数 885
作問者 :
yuki2006
Problem Statement
You are at a conveyor belt sushi restaurant.
$N$ plates of sushi come by in order. The deliciousness of each of the N plates of sushi is represented by \(V_i\).
You can take a plate of sushi when it comes in front of you, but under this restaurant's rules,
you cannot take plates twice in a row.
Of course, you also cannot take sushi that has already passed in front of you.
Find the maximum total deliciousness you can obtain.
The sushi does not come around a second time.
Input
\(N \) \(V_1\,V_2\,V_3 \ldots V_N \)
The first line contains the number of sushi plates \(N (1\le N \le 1000)\).
The second line contains the deliciousness values \( V_i (1\le V_i \le 100,1 \le i \le N) \), separated by single-byte spaces.
Output
Output the maximum total deliciousness you can obtain.
Sample
Sample 1
Input
4 1 2 3 4
Output
6
Ways of taking the sushi include taking the 1st and 3rd plates, taking the 1st and 4th plates, and taking the 2nd and 4th plates, among others, but
taking the 2nd and 4th plates gives the maximum deliciousness.
Sample 2
Input
4 5 4 4 9
Output
14
Taking the 1st and 4th plates gives the maximum total deliciousness.
Sample 3
Input
7 1 2 9 10 1 1 4
Output
16
Taking 2, 10, 4 gives the maximum of 16.
You must deliberately skip the two plates after 10.
Sample 4
Input
1 100
Output
100
There may be only one plate.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。