记录编号	200909	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战II]燃灵之链	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.232 s
提交时间	2015-10-29 18:34:51	内存使用	76.80 MiB

#include <fstream>
#include <ctime>
#define N 10010
#define M 1001
using namespace std;
typedef int ll;
ifstream in("KPengshuangcang.in");
ofstream out("KPengshuangcang.out");
int n,K;
ll f[N][M][2]={0},a[N]={0};//其实不用long long 也可以
ll INF=1;
ll lmax(ll a,ll b)
{
	if(a>b)return a;
	return b;
}
void read()
{
	int i;
	INF=(INF<<30);
	in>>n>>K;
	for(i=1;i<=n;i++)in>>a[i];
}
void work()
{
	int i,j,k,limit;
	for(i=1;i<=n;i++)
	{
		for(k=0;k<=K;k++)
		{
			f[i][k][0]=f[i][k][1]=-INF;//很重要，否则前三个点Wa
		}
	}
	f[1][1][1]=a[1];
	for(i=1;i<=n;i++)f[i][0][0]=f[i][0][1]=0;
	for(i=2;i<=n;i++)
	{
		limit=(i+1)/2;//所谓常数优化
		for(k=1;k<=K&&k<=limit;k++)
		{
			//如果用滚动数组要注意细节
			f[i][k][0]=lmax(f[i-1][k][0],f[i-1][k][1]);
			f[i][k][1]=lmax(f[i-1][k][1]+a[i],f[i-1][k-1][0]+a[i]);
		}
	}
	out<<max(f[n][K][0],f[n][K][1])<<endl;
}
int main()
{
	//int start,end;
	read();
	work();
	return 0;
}