• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[51nod1052]最大M子段和

admin

11月 28, 2021

题目链接:

51nod1052

(f[i][j])表示选了(i)段,最后一个数是(j)的最大值。

有简单方程:(f[i][j]=Max(f[i-1][k],f[i][j-1])+a[j](k<j))

第一种是断开成为新一段,第二种是接着上一个。

那么再维护一个前缀最大值(g)就可以做到(O(nm))

注意滚动优化,空间开不下。

代码:

#include <cstdio>
typedef long long ll;

inline ll Max(const ll a,const ll b){return a>b?a:b;}
int n,m,a[5005];
ll f[2][5005],g[2][5005];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
			g[i&1][j]=Max(f[i&1][j]=Max(f[i&1][j-1],g[(i&1)^1][j-1])+a[j],g[i&1][j-1]);
	printf("%lld
",g[m&1][n]);
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。