4418. 选元素（动态规划）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
#define int long long
int f[N][N];
int n, k, m;
signed main()
{
    cin >> n >> k >> m;
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        for (int j = 1; j <= m; j++) 
            for (int z = max(i - k, 0ll); z < i; z++)
                f[i][j] = max(f[i][j], f[z][j - 1] + x);
    }
    int res = -1;
    for (int i = n - k + 1; i <= n; i++) 
        res = max(res, f[i][m]);
    cout << res << endl;
    return 0;
}

// 单调队列优化
#include <bits/stdc++.h>
using namespace std;
const int N=210;
typedef long long LL;
LL f[N][N];
int a[N];
int q[N];
int hh=0,tt=-1;
int n,k,x;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        LL q = a[i];
    }
    //f[i][j]表示当前已经选择了i个点，且最后一个点的位置是j的所有集合，属性max
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=x;i++){
        int hh=0,tt=-1;
        for(int j=0;j<=n;j++){
            if(hh<=tt && q[hh] + k < j ) hh++;
            if(hh<=tt) f[i][j] = f[i-1][q[hh]] + a[j];
            while(hh<=tt && f[i-1][q[tt]] <= f[i-1][j]) tt--;
            q[++tt] = j;
        }
    }
    LL res = -1;
    for(int i=n-k+1;i<=n;i++) res = max(res, f[x][i]);
    cout<<res<<endl;
    return 0;
}