1 second
256 megabytes
standard input
standard output
The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.
Given a sequence of n integers p1, p2, ..., pn.
You are to choose k pairs of integers:
in such a way that the value of sum 
is
maximal possible. Help George to cope with the task.
The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000).
The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ 109).
Print an integer in a single line — the maximum possible value of sum.
5 2 1 1 2 3 4 5
9
7 1 3 2 10 7 18 5 33 0
61
我是sb……
一道水水的dp
f[i][j]表示前j个取i段的最大价值，t[i]表示从i-m+1到i的区间和
f[i][j]=max(f[i][j-1],f[i-1][j-m]+t[j])
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define LL long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,k;
LL f[5010][5010];
LL a[5010],s[5010],t[5010];
int main()
{
n=read();m=read();k=read();
for (int i=1;i<=n;i++)a[i]=read();
for (int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for (int i=m;i<=n;i++)
t[i]=s[i]-s[i-m];
for (int i=1;i<=k;i++)
{
for (int j=m;j<=n;j++)f[i][j]=max(f[i][j-1],f[i-1][j-m]+t[j]);
}
printf("%I64d",f[k][n]);
}