ymhh 的 题解

写了 12 分钟，我是 fw。

考虑 DP。

一、思路

尝试

定义 $f[i]$ 表示求解 $1\sim i$ 的最大和。

若第 $i$ 个数不选，则操作必然用于其他位置：要么删除第 $i$ 个和第 $i-1$ 个数，要么就加上第 $i$ 个数。

因此会发现存在后效性：不知道上一个数选还是不选，考虑增加一维。

正解

定义 $f[i][0]$ 表示求解 $1\sim i$ 的最大和，且第 $i$ 个数不选；定义 $f[i][1]$ 表示求解 $1\sim i$ 的最大和，且第 $i$ 个数选。

显然：

$$f[i][1]=\max(f[i-1][0],f[i-1][1])+a[i]$$

$$f[i][0]=\max(f[i-2][0],f[i-2][1])$$

记得用 memset 将数组初始化为最小值！！！