首页 > 代码库 > Codeforces Round #267 Div2 C George and Job --DP
Codeforces Round #267 Div2 C George and Job --DP
题意：把长度为n的序列分成k个m长的连续小序列，这些连续小序列的和最大是多少。
解法：显然DP。
定义： dp[i][j] 为前 i 个元素分成j个m端，且 i 是第j个的末尾的最大和。
那么有： dp[i][j] = max(dp[i-1][j], dp[i-m][j-1]+sum[i]-sum[i-m])
5000*5000的空间，是有点大。。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;lll dp[5002][5001];lll a[5002],sum[5003];int main(){ int n,m,k; int i,j; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { sum[0] = 0; for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); sum[i] = sum[i-1]+a[i]; } for(i=0;i<=n;i++) for(j=0;j<=k;j++) dp[i][j] = 0; for(i=m;i<=n;i++) { dp[i][0] = max(dp[i][0],dp[i-1][0]); for(j=1;j<=k;j++) { dp[i][j] = max(dp[i][j],dp[i-1][j]); dp[i][j] = max(dp[i][j],dp[i-m][j-1]+sum[i]-sum[i-m]); } } cout<<dp[n][k]<<endl; } return 0;}
Codeforces Round #267 Div2 C George and Job --DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。