题解 | 星际勘探者

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m,n,k;
    cin>>m>>n>>k;
    vector<int>a(m+1);
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    vector<int>dp(k+1,-1);
    dp[0]=n;
    int maxenergy = n;
    for(int i=1;i<=m;i++){
        for(int j=k;j>=0;j--){

            int best = -1;

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

            dp[j]=best;
            maxenergy=max(maxenergy,dp[j]);
        }
    }
    cout << maxenergy << endl;

    return 0;
}