题意

考虑第一只兔子：我们可以在第二只兔子之前或之后选择它。如果它在第二只兔子之后被选择，那么从第二只兔子到最后一只兔子的解与第一只兔子无关；否则，我们会得到相同的结果，但在第二只兔子之前显然会是喂食的兔子。因此，我们有两种动态规划状态。

思路

定义两种动态规划状态：

1. $d0_i$ —— 将后缀 $i$ 作为一个独立任务时的答案。
2. $d1_i$ —— 如果该后缀的前一只兔子已经被喂食，则后缀 $i$ 的答案。

算法步骤

• 初始化：
  • $d0_n = a_n$
  • $d1_n = b_n$
• 从 $i = n-1$ 到 $1$ 递推：
  • $d0_i = \max(a_i + d1_{i+1},\ b_i + d0_{i+1})$
  • $d1_i = \max(b_i + d1_{i+1},\ c_i + d0_{i+1})$
• 最终答案为 $d0_1$

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是兔子的数量。
• 空间复杂度：$O(n)$ 或 $O(1)$（若只保留上一状态）。

代码说明

• 使用两个数组或两个变量分别存储 $d0$ 和 $d1$ 的值。
• 从后向前遍历，根据递推公式更新状态。
• 最终输出 $d0_1$ 即为所求答案。