记录编号 151807 评测结果 AAAAAAAAAA
题目名称 鱼儿仪仗队 最终得分 100
用户昵称 Gravatar水中音 是否通过 通过
代码语言 C++ 运行时间 0.056 s
提交时间 2015-03-11 08:01:00 内存使用 2.60 MiB
显示代码纯文本
/*
f[i]为在i-k-1到i-1范围内选取最小的f值加上w[i]
表示的含义为在选上i的前提下,之前所有所选的数字之和最小
--Aiky   ∑(っ °Д °;)っ
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define MM 100010
long long int w[MM]={0},que[MM]={0},f[MM]={0};
long long int n,k,Sum=0,ans,i,head=1,tail=0;

int main()
{
	freopen("guardb.in","r",stdin);
	freopen("guardb.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(i=1;i<=n;i++)
	scanf("%lld",&w[i]),Sum+=w[i];
	for(k++,i=1;i<=k;i++)
	{
		while(tail>head&&w[ que[tail] ]>w[i])tail--;
		f[i]=w[i];que[++tail]=i;
	}
	for(n++,k--;i<=n;i++)
	{
		while(tail>head&&(que[tail]-que[head]>k))head++;
		f[i]=f[ que[head] ]+w[i];
		while(tail>head&&(f[ que[tail] ]>f[i]))tail--;
		que[++tail]=i;
	}
	ans=Sum-f[n];
	printf("%lld\n",ans);
	return 0;
}