CF467C George and Job

CF467C George and Job

使用luogu Romote judge

luoguの翻译de su

状态定义：f[i][j]表示在第i时，已经选了j段时的最优值

#include<cstdio> 
#include<algorithm>
#include<iostream>
using std::cin;
using std::cout;
using std::max;
long long f[5010][5010],base[5010];
int main() 
{
	cin.sync_with_stdio(false);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>base[i];
		base[i]+=base[i-1];
	}
	for(int i=m;i<=n;i++)
		for(int j=1;j<=k;j++)
			f[i][j]=max(f[i-1][j],f[i-m][j-1]+base[i]-base[i-m]) ;
	cout<<f[n][k];
	return 0;
}

明天再补吧，我要溜了