• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces467C

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

George and Job

 CodeForces - 467C 

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 ≤ nri - 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 nm 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.

Examples

Input
5 2 1
1 2 3 4 5
Output
9
Input
7 1 3
2 10 7 18 5 33 0
Output
61

sol:题意比较gou,用 K 条长度为 m 的不相交线段覆盖一段长度为 n 的数列,使得覆盖到的和最大
XJBdp应该不难,n2dp即可完美AC此题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=5005;
int n,m,K;
ll Cost[N],Qzh[N];
ll dp[N][N];
int main()
{
    int i,j;
    R(n); R(m); R(K);
    for(i=1;i<=n;i++) R(Cost[i]);
    for(i=1;i<=n;i++) Qzh[i]=Qzh[i-1]+Cost[i];
    dp[0][0]=0;
    for(j=1;j<=K;j++)
    {
        for(i=j*m;i<=n;i++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+Qzh[i]-Qzh[i-m]);
        }
    }
    Wl(dp[n][K]);
    return 0;
}
/*
Input
5 2 1
1 2 3 4 5
Output
9

Input
7 1 3
2 10 7 18 5 33 0
Output
61
*/
View Code

 

 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap