time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
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.
Input
The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000).
The second line contains nintegers p1, p2, ..., pn (0 ≤ pi ≤ 109).
Output
Print an integer in a single line — the maximum possible value of sum.
Sample test(s)
input
5 2 1 1 2 3 4 5
output
9
input
7 1 3 2 10 7 18 5 33 0
output
61
题解
dp。用一个前缀和优化即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
int n,m,K;
ll sum[5002],f[5002][5002];
void init()
{
scanf("%d%d%d",&n,&m,&K);
int i; ll x;
for(i=1;i<=n;i++)
{scanf("%I64d",&x); sum[i]=sum[i-1]+x;}
}
void dp()
{
int i,j;
//ll ans;
for(i=1;i<=n;i++)
for(j=1;j<=K;j++)
{if(j*m>i) continue;
f[i][j]=max(f[i][j],f[i-1][j]);
f[i][j]=max(f[i][j],f[i-m][j-1]+sum[i]-sum[i-m]);
//ans=max(ans,f[i][j]);
}
printf("%I64d\n",f[n][K]);
}
int main()
{
init(); dp();
return 0;
}