题目描述

有 $n$ 个礼物排成一排，每个礼物有一个快乐值 $a[i]$。

小明想选一些礼物，但有两个相邻的礼物不能同时选（因为它们会"打架"而损坏）。

请问小明最多能获得的总快乐值是多少？

输入格式

第一行一个正整数 $n$，表示礼物的个数。

第二行 $n$ 个整数 $a[1], a[2], \dots, a[n]$，表示每个礼物的快乐值。

输出格式

输出一个整数，表示能获得的最大总快乐值。

样例输入

5
3 2 5 4 1

样例输出

9

样例解释

选择第 $1$ 个（快乐值 $3$）、第 $3$ 个（快乐值 $5$）、第 $5$ 个（快乐值 $1$）， 总和 $= 3 + 5 + 1 = 9$，且它们互不相邻，这是最优方案。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a[i] \le 10000$。

提示

• 考虑用动态规划求解。定义 $dp[i]$ 表示前 $i$ 个礼物中能获得的最大快乐值。
• 对于第 $i$ 个礼物，有两种选择：
  • 不选：则 $dp[i] = dp[i-1]$
  • 选：则第 $i-1$ 个不能选，$dp[i] = dp[i-2] + a[i]$
  • 取两者的较大值：$dp[i] = \max(dp[i-1], dp[i-2] + a[i])$
• 边界条件：$dp[0] = 0$，$dp[1] = a[1]$。