首页 > 代码库 > Codeforces Round #267 (Div. 2) C
Codeforces Round #267 (Div. 2) C
题目:
C. George and Job
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputThe 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.
Sample test(s)
input
5 2 1 1 2 3 4 5
output
9
input
7 1 3 2 10 7 18 5 33 0
output
61
题意分析:
DP一下。dp[I][j]存前i有j组的最大值。
状态转移方程:
if(i-m>=0) dp[i][j] = max(dp[i][j],max(dp[i-1][j],dp[i-m][j-1]+b[i]-b[i-m])) ;
else
<span style="white-space:pre"> </span>dp[i][j] = max(dp[i][j],dp[i-1][j]) ;其中b[i]存前i项a[i]的和。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long dp[5005][5005] ; long long a[65555] ; long long b[65555] ; int main() { int n,m,k ; cin>>n>>m>>k; int i,j; for(i=1;i<=n;i++) { cin>>a[i]; b[i] = b[i-1] + a[i] ; } for(i=1;i<=n;i++) { for(j=1;j<=k;j++) { if(i-m>=0) dp[i][j] = max(dp[i][j],max(dp[i-1][j], dp[i-m][j-1]+b[i]-b[i-m])) ; else dp[i][j] = max(dp[i][j],dp[i-1][j]) ; } } cout<<dp[n][k]<<endl; return 0 ; }
Codeforces Round #267 (Div. 2) C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。