当前位置：首页 > news >正文

打卡信奥刷题（3195）用C++实现信奥题 P8102 「LCOI2022」 Cow Insertion

news 2026/5/1 23:05:58

P8102 「LCOI2022」 Cow Insertion

题目背景

Farmer John 迎来了新奶牛——Bessie。每个奶牛都会有一定的开心值，Farmer John 希望 Bessie 能更幸福的生活在这里。

题目描述

牛棚里原来有nnn头奶牛，开心值的感染距离mmm，并且aia_iai表示原来牛棚中第i(1≤i≤n)i(1\le i\le n)i(1≤i≤n)头牛的开心值。并且，Bessie 同样拥有一个开心值AAA。

整个牛棚的开心值是∑i=1n−m+1 max⁡i≤j≤i+m−1 aj\sum\limits_{i=1}^{n-m+1}\ \max\limits_{i\le j\le i+m-1}\ a_ji=1∑n−m+1i≤j≤i+m−1maxaj，Bessie 可以住在任意两头牛的中间或起始以及最后。Farmer John 想知道：Bessie 来这里之后，整个牛棚的开心值最大为多少。

输入格式

第一行包含三个整数n,m,An,m,An,m,A。分别表示为奶牛个数，开心值的感染距离，以及 Bessie 的开心值。

接下来一行，包含nnn个数aia_iai，表示原来牛棚中第i(1≤i≤n)i(1\le i\le n)i(1≤i≤n)头牛的开心值。

输出格式

仅一行，表示 Bessie 来这里之后，整个牛棚的开心值的最大值。

输入输出样例 #1

输入 #1

3 2 50 60 100 70

输出 #1

说明/提示

【样例解释】

当 Bessie 在第一个位置时（50,60,100,7050,60,100,7050,60,100,70），整个牛棚的开心值的最大值为max⁡{60,50}+max⁡{60,100}+max⁡{100,70}\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{60,100}+\max\cases{100,70}max{60,50}+max{60,100}+max{100,70}，即60+100+100=26060+100+100=26060+100+100=260。
当 Bessie 在第二个位置时（60,50,100,7060,50,100,7060,50,100,70），整个牛棚的开心值的最大值为max⁡{60,50}+max⁡{50,100}+max⁡{100,70}\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{50,100}+\max\cases{100,70}max{60,50}+max{50,100}+max{100,70}，即60+100+100=26060+100+100=26060+100+100=260。
当 Bessie 在第三个位置时（60,100,50,7060,100,50,7060,100,50,70），整个牛棚的开心值的最大值为max⁡{60,100}+max⁡{100,50}+max⁡{50,70}\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,50}+\max\cases{50,70}max{60,100}+max{100,50}+max{50,70}，即100+100+70=270100+100+70=270100+100+70=270。
当 Bessie 在第四个位置时（60,100,70,5060,100,70,5060,100,70,50），整个牛棚的开心值的最大值为max⁡{60,100}+max⁡{100,70}+max⁡{70,50}\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,70}+\max\cases{70,50}max{60,100}+max{100,70}+max{70,50}，即70+100+100=27070+100+100=27070+100+100=270。

显然，整个牛棚的开心值的最大值为max⁡{260,260,270,270}=270\newcommand{\cases}[1]{\{#1\}}\max\cases{260,260,270,270}=270max{260,260,270,270}=270。

【数据范围与约定】

subtask	n≤n\len≤	分值
111	5×1025\times10^25×102	101010
222	5×1035\times10^35×103	202020
333	5×1065\times10^65×106	707070

对于100%100\%100%的数据，1≤m≤n1\le m\le n1≤m≤n，0≤ai,A≤1000\le a_i, A\le1000≤ai,A≤100。

C++实现

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;longlongf[5000010],a[5000010],g[5000010];intq[5000010],st=1,ed;intmain(){intn,m;longlongA;scanf("%d%d%lld",&n,&m,&A);longlongsum=A;for(inti=1;i<=n;i++){scanf("%lld",a+i);sum+=a[i];if(st<=ed&&i-q[st]>=m-1)st++;while(st<=ed&&a[q[ed]]<a[i])ed--;q[++ed]=i;if(i>=m-1)f[i]=a[q[st]];}// 单调队列求 f 数组if(m==1){printf("%lld\n",sum);return0;}// 特判st=1,ed=0;for(inti=1;i<=n;i++){if(st<=ed&&i-q[st]>=m)st++;while(st<=ed&&a[q[ed]]<a[i])ed--;q[++ed]=i;if(i>=m)g[i]=a[q[st]];}// 清空队列，不另外开新数组，节省空间for(inti=m+1;i<=n;i++)g[i]+=g[i-1];for(inti=m;i<=n;i++)f[i]=max(A,f[i])+f[i-1];longlongans=0;for(inti=0;i<=n;i++)ans=max(ans,g[max(i-m+1,0)]+g[n]-g[i]+f[i]-f[max(i-m,0)]);printf("%lld\n",ans);return0;}