Untitled

mail@pastecode.io avatar
unknown
plain_text
19 days ago
1.3 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // input output
    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    vector<vector<int>> dp(n, vector<int>(k+1, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = k; j >= 0; j--) {
            int skip = A[i] + (i+1 < n && j+1 <= k ? dp[i+1][j+1] : 0);
            int next = i+1 < n ? dp[i+1][0] : 0;
            dp[i][j] = max(skip, next);
        }
    }
    
    cout << dp[0][0] << endl;
    
    return 0;
}

/*
// #1: Recursion + memo
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> A;
map<pair<int, int>, int> memo;

int solve(int i, int consecutive) {
    if (i >= n) return 0;
    
    pair<int, int> key = make_pair(i, consecutive);
    if (memo.count(key)) {
        return memo[key];
    }
    
    int next = 0, skip = 0;
    if (consecutive <= k) {
        next = A[i] + solve(i + 1, consecutive + 1);
    }
    
    skip = solve(i + 1, 0);
    
    int ans = max(next, skip);
    memo[key] = ans;
    return ans;
}

int main()
{
    // input output
    cin >> n >> k;
    
    A.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    
    int ans = solve(0, 0);
    cout << ans;
    return 0;
}
*/
Leave a Comment