[FZYZOJ 1300] Food

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

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;
}
Grade 5 Result dhaka 说:
2022年8月31日 16:44

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. Grade 5 Result dhaka BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


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