题目大意

从数组中选出$k$个长度为$m$的不相邻区间，求$k$个区间求和的最大值。

思路

序列求和不难联想到前缀和。呢么我们可以预处理出来所以可选的区间，然后做dp。

状态转移

$f[i][j]$表现从前$i$个区间里选，恰好选了$j$个区间的最大值。
呢么就可以分为第$i$个区间选不选。
$if(i-m<0)$ $f[i][j]=max(f[i-1][j],w[i])$;
$else$ $f[i][j]=max(f[i-1][j],f[i-m][j-1]+w[i])$;
至于为什么是$i-m$，是因为选了这个区间，由于题目限制，它前面的$m-1$个区间就不能选了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
ll n,m,k;
ll a[N],b[N];
ll w[N];
ll f[N][N];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    ll cnt=0;
    for(int i=1;i+m-1<=n;i++)
    {
        w[++cnt]=b[i+m-1]-b[i-1];//预处理区间
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i-m<0) f[i][j]=max(f[i-1][j],w[i]);//此时最多选择一个区间
            else f[i][j]=max(f[i-1][j],f[i-m][j-1]+w[i]);
        }
    }
    cout<<f[cnt][k];
    return 0;
}