题目大意 给定一个长度为 nnn 的数组 aia_iai ，表示在第 iii 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。 题解思路 这是经典的线性 DP。设 dp[i] 表示只考虑前 i 个位置能得到的最大收益，则第 i 个位置要么不选，要么选： * 不选 i：收益 dp[i-1] * 选 i：则 i-1 不能选，收益 dp[i-2] + a_i 所以递推为 dp[i]=max⁡(dp[i−1],dp[i−2]+ai).dp[i]=\max(dp[i-1], dp[i-2]+a_i). dp[i]=max(dp[i−1],dp[i−2]+ai ). 边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。 参考代码