在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
George and JobThe 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:
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 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 Output
9
Input
7 1 3 Output
61
#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 */
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论