首页 > 代码库 > cf_467C_George and Job

cf_467C_George and Job

2024-07-23 12:24:22   218人阅读

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 choosek 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 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 containsn 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
1 2 3 4 5
Output
9
Input
7 1 3
2 10 7 18 5 33 0
Output
61
情景就不赘述了，给你n个数p1~pn，要你求出这个数列中k段长为m的区间的元素之和的最大值。

要求区间元素和，当然想求出数列的前缀和来了。


二维dp，dp[i][j]表示在取到第i个元素的时候取j个m长度的区间之和的最大值。

dp[i][j]可由dp[i-1][j]不添加区间得到的,或者由dp[i-m][j-1]添加一个区间得到。

遂有状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+s[i]-s[i-m])，其中s是前缀和。


然后就是简单题了。


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long  dp[5005][5005];
int  main(){
	int  n,m,k;
	scanf ("%d%d%d",&n,&m,&k);//
	long long  a[5005],s[5005];
	memset(a,0,sizeof(a));
	memset(s,0,sizeof(s));
	memset(dp,0,sizeof(dp));
	for (int  i=1;i<=n;i++){
		scanf ("%I64d",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	for (int  i=m;i<=n;i++){
		for (int  j=1;j<=k;j++){
			dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+s[i]-s[i-m]);
		}
	}
	
	printf ("%I64d\n",dp[n][k]);
	return 0;
}

（ps：数据爆int）  :(






cf_467C_George and Job


联系
我们