不用O(n^3)朴素dp做，求助单调队列优化。

https://www.acwing.com/problem/content/4421/

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[5001],dp[5001][5001],k,x,q[5001][5001],ql[5001],qr[5001];
signed main()
{
    cin>>n>>k>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ql[i]=1;
        qr[i]=0;
    }
    memset(dp,0x80,sizeof(dp));
    //q[i][1]表示选了i个数的最优值
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=x;j++)
        {
            while(ql[j]<=qr[j]&&i-q[j][ql[j]]>k)ql[j]++;
        }
        for(int j=1;j<=min(i,x);j++)
        {
            if(j>1)
            {
                dp[i][j]=max(dp[i][j],dp[q[j-1][ql[j-1]]][j-1]+a[i]);
                if(dp[i][j]==11)
                cout<<"qaq  "<<q[j-1][ql[j-1]]<<'\n';
            }
            else
            {
                if(i<=k)
                {
                    dp[i][j]=a[i];
                }
            }
            /*if(dp[i][j]==10)
            {
                cout<<"qaq:"<<q[j-1][ql[j-1]]<<"\n";
            }*/
            while(ql[j]<=qr[j]&&dp[i][j]>=dp[q[j][qr[j]]][j])
            {
                qr[j]--;
                //cout<<"i:"<<i<<"   j: "<<j<<"    "<<"dp[i][j]:"<<""<<dp[i][j]<<"    ql[j]:"<<ql[j]<<"     qr[j]:"<<qr[j]<<"  dp[qr[j]][j] "<<dp[qr[j]][j]<<"\n";
            }
            q[j][++qr[j]]=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    int res=-1;
    for(int i=n-k+1;i<=n;i++)
    {
        res=max(res,dp[i][x]);
    }
    cout<<res;
}