题目
传送门:QWQ
分析
dp基础题。
$ dp[i][j] $表示前i个数分成j组的最大和。
转移显然。
吐槽:做cf题全靠洛谷翻译苟活。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
ll dp[maxn][maxn], sum[maxn], a[maxn];
ll Sum(int l,int r){/* printf("---%d %d\n",l,r);*/ return sum[r]-sum[l-];}
int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
scanf("%I64d",&a[i]); sum[i]=sum[i-]+a[i];
}
for(int j=;j<=k;j++){
for(int i=;i<=n;i++){
dp[i][j]=dp[i-][j];
if(i>=m ) dp[i][j]=max(dp[i][j],dp[i-m][j-]+Sum(i-m+,i));
}
}
printf("%I64d\n",dp[n][k]);
return ;
}