[FZYZOJ 1300] Food
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;
}
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.
2023年4月28日 15:41
Board Model Paper 2023 Aspirants who had Registered for the Maha Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. model-papers.com Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.