经典Dp,果断记忆化……
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
using namespace std;
#define MAXN 10000 + 10
#define MAXM 500 + 10
int f[MAXN][MAXM],n,m,d[MAXN];
int dfs(int i,int j)
{
if (i==0) return 0;
if (f[i][j]) return f[i][j];
if (i&&!j) f[i][j]=dfs(i-1,0);
if (j)
f[i][j]=dfs(i-1,j-1)+d[i];
else
{
for (int k=min(i,m);k>0;k--)
{
f[i][j]=max(f[i][j],dfs(i-k,k));
}
}
return f[i][j];
}
int main()
{
// freopen("running.in","r",stdin);
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&d[i]);
printf("%d\n",dfs(n,0));
// while (1);
return 0;
}