题解 | #小红的星尘收集#

题目链接

题目描述

小红在银河中发现了一个线性的星尘序列，每个位置的星尘都有固定的能量值 $a_i$ 。小红可以收集星尘为飞船充能，但由于“量子纠缠”现象，如果收集了第 $i$ 个位置的星尘，则相邻的第 $i-1$ 个和第 $i+1$ 个位置的星尘会消散。请帮小红计算在不违反规则的前提下，能收集到的最大能量总和。

输入：

一行由若干个空格分隔的整数，代表序列中每团星尘的能量值 $a_i$ 。

数据范围：

星尘总数 $n$ 满足： $1 < n < 500$
每个星尘的能量值 $a_i$ 满足： $0 \le a_i \le 10000$

输出：

一个整数，代表能收集到的最大能量总和。

解题思路

本题是一个经典的动态规划问题，即“不相邻子序列最大和”问题。

状态定义：设 $dp[i]$ 表示前 $i$ 个星尘中能够收集到的最大能量总和。
状态转移方程：对于第 $i$ 个星尘（从 $0$ 开始计数），有两种选择：
- 不收集第 $i$ 个星尘：此时最大能量等于前 $i-1$ 个星尘的最大能量，即 $dp[i] = dp[i-1]$ 。
- 收集第 $i$ 个星尘：此时不能收集第 $i-1$ 个星尘，因此最大能量等于 $a_i$ 加上前 $i-2$ 个星尘的最大能量，即 $dp[i] = a_i + dp[i-2]$ 。综上所述： $dp[i] = \max(dp[i-1], a_i + dp[i-2])$ 。
初始化与边界情况：
- 根据数据范围 $1 < n < 500$ ，序列中至少有两个星尘。
- $dp[0] = a_0$
- $dp[1] = \max(a_0, a_1)$
复杂度分析：
- 时间复杂度： $\mathcal{O}(n)$ 。
- 空间复杂度： $\mathcal{O}(n)$ ，可以使用变量优化至 $\mathcal{O}(1)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

typedef long long LL;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<LL> a;
    LL val;
    while (ss >> val) {
        a.push_back(val);
    }

    int n = a.size();
    if (n == 1) {
        cout << a[0] << endl;
        return 0;
    }

    vector<LL> dp(n);
    dp[0] = a[0];
    dp[1] = max(a[0], a[1]);
    for (int i = 2; i < n; ++i) {
        dp[i] = max(dp[i - 1], a[i] + dp[i - 2]);
    }

    cout << dp[n - 1] << endl;
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Long> a = new ArrayList<>();
        while (sc.hasNextLong()) {
            a.add(sc.nextLong());
        }

        int n = a.size();
        if (n == 1) {
            System.out.println(a.get(0));
            return;
        }

        long[] dp = new long[n];
        dp[0] = a.get(0);
        dp[1] = Math.max(a.get(0), a.get(1));
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], a.get(i) + dp[i - 2]);
        }

        System.out.println(dp[n - 1]);
    }
}

def solve():
    data = list(map(int, input().split()))

    n = len(data)
    if n == 1:
        print(data[0])
        return

    dp = [0] * n
    dp[0] = data[0]
    dp[1] = max(data[0], data[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i - 1], data[i] + dp[i - 2])
        
    print(dp[n - 1])

if __name__ == "__main__":
    solve()

算法及复杂度

算法：动态规划。
时间复杂度： $\mathcal{O}(n)$ - 仅需一次遍历星尘序列。
空间复杂度： $\mathcal{O}(n)$ - 使用了 $dp$ 数组存储中间状态。