51nod 1052 最大M子段和

设 dp[i][j] 表示前i个元素，选取j个区间，且第i个元素必选的情况下的最大字段和。

dp[i][j]=max(dp[i-1][j]+a[i],max(dp[k,j-1]+a[i]));

0≤k≤i-1

空间压缩一下，前缀也dp一下就好了。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=5050;
long long a[MAXN],dp[2][MAXN],mxdp[2][MAXN];

int main()
{
	long long n,m,i,j,ans;
	while(~scanf("%lld%lld",&n,&m))
	{
		for(i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		memset(dp,0,sizeof(dp));
		memset(mxdp,0,sizeof(mxdp));
		ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=min(i,m);j++)
			{
				dp[i&1][j]=max(dp[i&1^1][j]+a[i],mxdp[i&1^1][j-1]+a[i]);
				ans=max(ans,dp[i&1][j]);
				mxdp[i&1][j]=max(mxdp[i&1^1][j],dp[i&1][j]);
			}
		}
		printf("%lld\n",ans);
	}
}