题解 | #星际勘探者#

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

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

    int m, n, k;
    cin >> m >> n >> k;

    vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
    }

    vector<long long> dp(k + 1, -1);
    dp[0] = n;

    long long max_overall_energy = n;

    for (int i = 0; i < m; ++i) { // 遍历每颗小行星 a[i]
        vector<long long> temp_dp = dp; // 使用临时数组防止状态干扰

        for (int j = 0; j <= k; ++j) {
            // 来源1: 不采集小行星 a[i]。
            // 从上一步的 dp[j] 状态转移而来。
            long long energy_from_no_collect = -1;
            if (dp[j] > 0) {
                energy_from_no_collect = dp[j] - 1;
            }

            // 来源2: 采集小行星 a[i]。
            // 从上一步的 dp[j-1] 状态转移而来。
            long long energy_from_collect = -1;
            if (j > 0 && dp[j - 1] > 0) {
                energy_from_collect = dp[j - 1] - 1 + a[i];
            }

            temp_dp[j] = max(energy_from_no_collect, energy_from_collect);
            max_overall_energy = max(max_overall_energy, temp_dp[j]);
        }
        dp = temp_dp;
    }

    cout << max_overall_energy << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] a = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
        }

        long[] dp = new long[k + 1];
        Arrays.fill(dp, -1);
        dp[0] = n;

        long maxOverallEnergy = n;

        for (int i = 0; i < m; i++) { // 遍历每颗小行星 a[i]
            long[] tempDp = Arrays.copyOf(dp, dp.length);

            for (int j = 0; j <= k; j++) {
                // 来源1: 不采集小行星 a[i]
                long energyFromNoCollect = -1;
                if (dp[j] > 0) {
                    energyFromNoCollect = dp[j] - 1;
                }

                // 来源2: 采集小行星 a[i]
                long energyFromCollect = -1;
                if (j > 0 && dp[j - 1] > 0) {
                    energyFromCollect = dp[j - 1] - 1 + a[i];
                }

                tempDp[j] = Math.max(energyFromNoCollect, energyFromCollect);
                maxOverallEnergy = Math.max(maxOverallEnergy, tempDp[j]);
            }
            dp = tempDp;
        }

        System.out.println(maxOverallEnergy);
    }
}

def main():
    m, n, k = map(int, input().split())
    a = list(map(int, input().split()))

    # dp[j] 表示在当前步骤后，采集了j次的最大能量
    dp = [-1] * (k + 1)
    dp[0] = n

    max_overall_energy = n

    for i in range(m): # 遍历每颗小行星 a[i]
        temp_dp = list(dp)

        for j in range(k + 1):
            # 来源1: 不采集小行星 a[i]
            energy_from_no_collect = -1
            if dp[j] > 0:
                energy_from_no_collect = dp[j] - 1

            # 来源2: 采集小行星 a[i]
            energy_from_collect = -1
            if j > 0 and dp[j - 1] > 0:
                energy_from_collect = dp[j - 1] - 1 + a[i]
            
            # 新的 dp[j] 是两种来源中的最大值
            temp_dp[j] = max(energy_from_no_collect, energy_from_collect)
            max_overall_energy = max(max_overall_energy, temp_dp[j])
        
        dp = temp_dp

    print(max_overall_energy)

if __name__ == "__main__":
    main()