记录编号	200767	评测结果	WWWAAAAWAA
题目名称	[ZLXOI 2015][异次元圣战II]燃灵之链	最终得分	60
用户昵称	Skyo	是否通过	未通过
代码语言	C++	运行时间	0.074 s
提交时间	2015-10-29 14:43:58	内存使用	0.40 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, mxf, ans, sum[10005], f[2][10005];

int main()
{
	freopen("KPengshuangcang.in","r",stdin);
	freopen("KPengshuangcang.out","w",stdout);
	
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) 
	{
		scanf("%d", sum+i);
		sum[i] += sum[i-1];
	}
	
	for(int i = 1; i <= m; i++)
	{
		mxf = 0;
		for(int j = 1; j <= n; j++)
		{
			f[i&1][j] = max(f[i&1][j-1], mxf + sum[j]);
			if(j > 1) mxf = max(mxf, f[!(i&1)][j-1]-sum[j]);
		}
	}
	
	for(int i = 1; i <= n; i++) ans = max(ans, f[m&1][i]);
	printf("%d", ans);
	return 0;
}