[FZYZOJ 1300] Food

tonyfang posted @ 2015年8月10日 22:59 in FZYZOJ with tags c++ FZYZOJ , 301 阅读

P1330 -- food

时间限制:1000MS

内存限制:131072KB

Description

超市的货架上摆放着n种零食,每一种零食都有一个营养值w。因为有的零食是垃圾食品,所以营养值可以是负数,当然了,其它零食的营养值都大于等于0。小辰是一个爱偷懒的孩子,所以他希望所选取的零食在货架上是连续的一段。小辰很贪吃,所以他至少要选择min种零食,可是零花钱有限,他所选择的零食又不能超过max种。爱偷懒的小辰想问问你怎么选择他能获得的总营养值最高?

Input Format

第一行三个整数:n,min,max。中间用空格隔开。

第2到n+1 行每行一个整数w[I]。

Output Format

一个整数表述最大的总营养值。

Sample Input

10 5 6
432
-245
3256
-42
-542
25
52
-2
3636
-341

Sample Output

3370

Hint

30%:min,max,n<=10000

100%:min,max,n<=100000。所有输入数据在longint范围以内。(C++为long long)

题解

单调队列。

先用s[i]维护[1,i]前缀和。然后使s[Min-1]最小,维护前缀和的单调递增序列即可。

# include <stdio.h>
using namespace std;
long long n,Min,Max,s[100010],q[100010],ans,head,tail;
int main() {
	scanf("%lld%lld%lld",&n,&Min,&Max);
	for (int i=1;i<=n;++i) {
		scanf("%lld",&s[i]);
		s[i]+=s[i-1];
	}
	for (int i=Min;i<=n;++i) {
		while(head<=tail && s[q[tail]]>s[i-Min]) tail--;
		q[++tail]=i-Min;
		while(i-q[head]>Max) ++head;
		if(s[i]-s[q[head]]>ans) ans=s[i]-s[q[head]];
	}
	printf("%lld\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter