← 返回题目列表

AtCoder · awc0065_c

C. 为花坛选择鲜花

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥有 N 他的花园里排列着一排花坛。

每个花坛的编号为 1 to N。种一朵花在 i第个花坛的美丽值为 A_i。然而,如果两个相邻的花坛都种植花朵,根部会相互干扰,两朵花都会枯萎。因此,两地都不允许种花。 i-th 和 (i+1)第花坛(1 \leq i \leq N-1).

高桥将根据此条件选择一些花坛种植花卉。每个花坛是否种植花卉都是独立决定的,任何花坛都不能种植超过一次。也可以不种花,这样整体的美感就出来了 0.

找出从种植鲜花的花坛中获得的最大可能的总体美感。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N,代表花坛数量。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每个花坛种植一朵花所获得的美丽值。
  • A_i 代表着在其中种植一朵花所获得的美丽 i第花坛。

输出

用一行打印高桥可以实现的最大整体美感。


示例输入 1

5
3 2 5 1 4

示例输出 1

12

示例输入 2

8
10 1 10 1 10 1 10 1

示例输出 2

40

示例输入 3

15
100 200 300 150 50 400 10 500 250 80 600 30 450 20 350

示例输出 3

2700