Codeforces Round #267 (Div. 2)
|
C. George and Job
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: [l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m), in such a way that the value of sum Input
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). Output
Print an integer in a single line — the maximum possible value of sum. Sample test(s)
Input
5 2 1 Output
9 Input
7 1 3 Output
61 |
题意：
给出n,m,k，给出由n个数组成的序列，在其中选出k组不重叠的连续m个数，使选择的数的和最大。
题解：
DP。
f[i][j],表示在[1,i]中选了j个区间得到的最大的和。
由于要经常求某连续m个数的和，可以先预处理出所有连续m个数的和，sum[i]表示以i为结尾的连续m个数的和。
最后结果为f[n][k]。
状态转移：
mf1(f);///全部置为-1
FOR(i,,n) f[i][]=;
FOR(i,,n){
FOR(j,,k){
f[i][j]=f[i-][j];
if(i-m>= && f[i-m][j-] != -) f[i][j]=max(f[i][j],f[i-m][j-]+sum[i]);
}
}
全代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const double eps=1e-;
const double pi=acos(-1.0);
int a[];
ll sum[];
ll f[][];///f[i][j],到i时选了j个区间
int n,m,k;
int main(){
int i,j;
RD3(n,m,k);
FOR(i,,n){
RD(a[i]);
}
ll sm=;
FOR(i,,n){
sm+=a[i];
if(i>=m){
sum[i]=sm;
sm-=a[i-m+];
}
}
mf1(f);///全部置为-1
FOR(i,,n) f[i][]=;
FOR(i,,n){
FOR(j,,k){
f[i][j]=f[i-][j];
if(i-m>= && f[i-m][j-] != -) f[i][j]=max(f[i][j],f[i-m][j-]+sum[i]);
}
}
printf("%I64d\n",f[n][k]);
return ;
}