Codeforces Round #267 (Div. 2) C George and Job

George and Job

给你n个数，每一段有m个数，取k段，并且每一段区间没有交叉。

dp[i][j]表示到第i个数时取了j段区间的最大和。

dp[i][j]=max(不取区间[i-m+1,i]，取区间[i-m+1,i]);

dp[i][j]=max(dp[i-1][j]，dp[i-m][j-1]+区间[i-m+1,i]的区间和)

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+100;
typedef long long ll;

ll a[N];
ll p[N];
ll dp[N][N];
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	p[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]=a[i]+p[i-1];
	}

	dp[0][0]=0;
	for(int i=m;i<=n;i++){
		for(int j=1;j<=k;j++){
			dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+p[i]-p[i-m]);
		}
	}
	
	cout<<dp[n][k]<<endl;
	return 0;
}