dp[i][j]代表前i个数中拿了j次m个数的最优情况
dp[i][j]=max(dp[i][j],dp[i-1][j-1],dp[i-m][j-1]+sum(i)-sum(i-m));
5000*5000从空间上来说浪费太多,故用滚动数组更好,细节自己处理一下
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5010;
int n, m, k;
int f[N][N];
int sum[N], nums[N];
signed main(){
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; i++){
scanf("%lld", &nums[i]);
sum[i] = sum[i-1] + nums[i];
}
for(int i = m; i <= n; i++)
for(int j = 1; j <= k; j++)
f[i][j] = max(f[i-1][j], f[i-m][j-1] + sum[i] - sum[i-m]);
printf("%lld", f[n][k]);
return 0;
}