51 nod 1052 最大M子段和

http://www.51nod.com/Challenge/Problem.html#problemId=1052

f[i][j][0/1]表示前i个数，划出了j段，第i个数可以不必使用/必须使用的最大值

如果第i个数必须使用，那么它可以加入前一个数所在的那一段(此时它的前一个数必须使用），也可以自成一段（此时对前一个数没有限制）
所以(f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+a[i])

如果第i个数可以不必使用，那么它可以用也可以不用
所以(f[i][j][0]=max(f[i-1][j][0],f[i][j][1]))

滚动数组

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define N 5001

int a[N];
long long f[2][N][2];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	f[0][0][0]=0;
	for(int i=1;i<=m;++i) f[0][i][0]=f[0][i][1]=-1e15;
	int p=0,q=1;
	for(int i=1;i<=n;++i,swap(p,q))
		for(int j=1;j<=min(i,m);++j)
		{
			f[q][j][1]=f[p][j][1]+a[i];
			f[q][j][1]=max(f[q][j][1],f[p][j-1][0]+a[i]);
			f[q][j][0]=max(f[q][j][1],f[p][j][0]);
		}
//	for(int i=0;i<=n;++i) 
//	{
//		for(int j=0;j<=min(i,m);++j)
//			printf("(%lld %lld) ",f[i][j][0],f[i][j][1]);
//		printf("
");
//	}	
	printf("%lld",f[p][m][0]); 
}