nyoj1184为了肾六【dp】

nyoj1184为了肾六【dp】

为了肾六

描述

最近肾六很流行，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，pn(0 ≤ pi ≤ 10^9).

输出

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

样例输入

5 2 11 2 3 4 57 1 32 10 7 18 5 33 0

样例输出

961

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=5010;
long long num[maxn];
long long dp[maxn][maxn];//前i个数分j个分组时的最大和
long long MAX(long long a,long long b){return a>b?a:b;
} 
int main()
{int n,m,i,j,k,t;while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(i=1;i<=n;++i){scanf("%lld",&num[i]);num[i]=num[i]+num[i-1];}memset(dp,0,sizeof(dp));for(i=1;i<=k;++i){for(j=m;j<=n;++j){dp[i][j]=MAX(dp[i][j-1],dp[i-1][j-m]+num[j]-num[j-m]);//dp[i-1][j-m]增加一个新分组//dp[i][j-1]前j-1个数分为i个分组时的最大值}}printf("%lldn",dp[k][n]);}return 0;
}