官方题解

题目大意

给定一个长度为 $n$ 的数组 $a_i$，表示在第 $i$ 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。

题解思路

这是经典的线性 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]+a_i).$$

边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> dp(n + 1, 0);
    vector<char> take(n + 1, 0);

    if (n >= 1) {
        if (a[1] > 0) {
            dp[1] = a[1];
            take[1] = 1;
        } else {
            dp[1] = 0;
            take[1] = 0;
        }
    }

    for (int i = 2; i <= n; i++) {
        long long v1 = dp[i - 1];
        long long v2 = dp[i - 2] + a[i];
        if (v2 > v1) {
            dp[i] = v2;
            take[i] = 1;
        } else {
            dp[i] = v1;
            take[i] = 0;
        }
    }

    vector<int> ans;
    int i = n;
    while (i >= 1) {
        if (take[i]) {
            ans.push_back(i);
            i -= 2;
        } else {
            i -= 1;
        }
    }
    reverse(ans.begin(), ans.end());

    cout << dp[n] << "\n";
    cout << ans.size() << "\n";
    for (int j = 0; j < (int)ans.size(); j++) {
        if (j) cout << ' ';
        cout << ans[j];
    }
    cout << "\n";
    return 0;
}