给定一个长度为 n 的整数数列 a1,a2,…,an。
请你选择 k 个数对 [l1,r1],[l2,r2],…,[lk,rk],要求所选数对满足:
1≤l1≤r1<l2≤r2<…<lk≤rk≤n。 对于 1≤i≤k,ri?li+1=m 均成立。 设 sum=∑i=1k∑j=liriaj,sum 的值应尽可能大。 请你输出 sum 的最大可能值。
输入格式 第一行包含三个整数 n,m,k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式 一个整数,表示 sum 的最大可能值。
数据范围 前 6 个测试点满足 1≤m×k≤n≤20。 所有测试点满足 1≤m×k≤n≤5000,0≤ai≤109。
输入样例1: 5 2 1 1 2 3 4 5 输出样例1: 9 输入样例2: 7 1 3 2 10 7 18 5 33 0 输出样例2: 61
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,t,a[5005],s[5005],f[5005][5005];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
cin>>a[i];s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;++i)
{
if(i-m<0)continue;
for(int j=1;j<=k;++j)
{
t=s[i]-s[i-m];
f[i][j]=max(f[i-1][j],f[i-m][j-1]+t);
}
}
cout<<f[n][k];
return 0;
}
|