首页 > 代码库 > codeforces 467C George and Job dp
codeforces 467C George and Job dp
题目大意：n个数排成一列，在这n个数中取k段连续的长度为m的序列并最大化。
dp[i][j]表示前 i 个数中取 j 段的最大值。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;ll dp[5100][5100],sum[5100];int n,m,k;int main(){ scanf("%d%d%d",&n,&m,&k); int i,j,x; sum[0]=0; for(i=1;i<=n;i++) { scanf("%d",&x); sum[i]=sum[i-1]+x; } memset(dp,0,sizeof(dp)); for(i=m;i<=n;i++) for(j=1;j<=k;j++) dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]); printf("%I64d\n",dp[n][k]); return 0;}
codeforces 467C George and Job dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。