为了肾六(dp)

 

为了肾六

时间限制：4000 ms  |  内存限制：210535 KB

难度：2

 

描述

最近肾六很流行，goshawk看身边的朋友都用上了apple。自己还用着W年前的Samsung。于是决定去IT公司打工，都是为了肾六。现在上司让他解决下面的一个小问题，但是goshawk没学好算法，被这个问题难住了，聪明的你帮帮他吧。

给一个n个整数的序列p₁,p₂,p₃.....p_n。你要以下面的方式选k对整数。[l1, r1], [l2, r2], ..., [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < ... < lk ≤ rk ≤ n; ri - li + 1 = m),  为了让这个表达式的值尽可能大。赶快帮他解决这个问题吧。

 

输入

第一行包含三个整数n,m,和k(1 ≤ (m × k) ≤ n ≤ 5000)。第二行包含n个整数p1，p2,p3.....pn(0 ≤ pi ≤ 10^9).

输出

单行输出一个整数。最大和的值。

样例输入

5 2 1
1 2 3 4 5
7 1 3
2 10 7 18 5 33 0

样例输出

9
61

题解：

dp[i][j]代表j个人选i组数据的最大值

dp[i][j] = max(dp[i][j], dp[i-1][j-M]+(a[j-M+1] + ...+a[j]))

代码：

 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x); 
typedef long long LL;
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
#define T_T while(T--)
const int INF=0x3f3f3f3f;
const int MAXN=100010;
LL seq[MAXN];
LL dp[2][MAXN];
int main(){
	int n,m,k;
	while(~scanf("%d%d%d",&n,&m,&k)){
		for(int i=1;i<=n;i++)SL(seq[i]);
		mem(dp,0);
		for(int i=n;i>=1;i--)
			for(int j=i-m+1;j<i&&i-m+1>=1;j++)seq[i]+=seq[j];
		for(int i=1;i<=k;i++){
			for(int j=1;j<=n;j++){
				dp[i&1][j]=max(dp[i&1][j],dp[i&1][j-1]);
				dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-m]+seq[j]);
			}
		}
		PL(dp[k&1][n]);puts("");
	}
	return 0;
}