不相邻子集最小和

解题思路

目标是在不相邻约束下最小化子集和，且至少选 $1$ 个元素；数组可能含负数，不能当成「打家劫舍求最大和」。
线性 DP：设 $f$ 表示「选中当前位置」的最小和， $g$ 表示「不选当前位置且前面已至少选过一个」的最小和。
转移：不选 $a_i$ 时 $g'=\min(f,g)$ ；选 $a_i$ 时，前一位置必须未选，可接空集或旧的 $g$ ，即 $f'=a_i+\min(0,g)$ （若 $g$ 尚不合法则只取 $a_i$ ）。
答案为 $\min(f,g)$ 。和可能到 $-10^{14}$ 量级，使用 $64$ 位整数。

给定一个长度为 $n$ 的整数数组 $a$ ，从中选取若干不相邻元素（即任意两个被选中元素的下标之差大于 $1$ ），使得所选元素之和最小。要求至少选取一个元素。

第一行输入一个整数 $n$ （ $1 \le n \le 10^5$ ），表示数组长度。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $-10^9 \le a_i \le 10^9$ ）。

输出一个整数，表示不相邻子集的最小元素之和。

输入

5
3 -2 5 -1 -4

输出

-6

输入

3
2 -5 3

输出

-5

选择提交后点击「开始AI分析」