「CF467C」George and Job
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:
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.
Sample test(s)
input
|
1 2 |
5 2 1 1 2 3 4 5 |
output
|
1 |
9 |
input
|
1 2 |
7 1 3 2 10 7 18 5 33 0 |
output
|
1 |
61 |
题解
直接dp。。。二维+前缀和搞搞就好
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,k; ll sum[5005],a[5005],f[5005][5005]; int main() { n=read();m=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; f[m][1]=sum[m]; for(int i=m+1;i<=n;i++) for(int j=1;j<=k;j++) f[i][j]=max(f[i-1][j],f[i-m][j-1]+sum[i]-sum[i-m]); printf("%I64d",f[n][k]); return 0; } |
计数器 9787116
OI 课件=>
OI 课件=>
代码好像复制错了吧