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。整个牛棚的开心值是∑i1n−m1 max⁡i≤j≤im−1 aj\sum\limits_{i1}^{n-m1}\ \max\limits_{i\le j\le im-1}\ a_ji1∑n−m1​i≤j≤im−1max​aj​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输入 #13 2 50 60 100 70输出 #1270说明/提示【样例解释】当 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}即601001002606010010026060100100260。当 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}即601001002606010010026060100100260。当 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}即100100702701001007027010010070270。当 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}即701001002707010010027070100100270。显然整个牛棚的开心值的最大值为max⁡{260,260,270,270}270\newcommand{\cases}[1]{\{#1\}}\max\cases{260,260,270,270}270max{260,260,270,270}270。【数据范围与约定】subtaskn≤n\len≤分值1115×1025\times10^25×1021010102225×1035\times10^35×1032020203335×1065\times10^65×106707070对于100%100\%100%的数据1≤m≤n1\le m\le n1≤m≤n0≤ai,A≤1000\le a_i, A\le1000≤ai​,A≤100。C实现#includeiostream#includecstdio#includealgorithm#includecstringusingnamespacestd;longlongf[5000010],a[5000010],g[5000010];intq[5000010],st1,ed;intmain(){intn,m;longlongA;scanf(%d%d%lld,n,m,A);longlongsumA;for(inti1;in;i){scanf(%lld,ai);suma[i];if(stedi-q[st]m-1)st;while(steda[q[ed]]a[i])ed--;q[ed]i;if(im-1)f[i]a[q[st]];}// 单调队列求 f 数组if(m1){printf(%lld\n,sum);return0;}// 特判st1,ed0;for(inti1;in;i){if(stedi-q[st]m)st;while(steda[q[ed]]a[i])ed--;q[ed]i;if(im)g[i]a[q[st]];}// 清空队列不另外开新数组节省空间for(intim1;in;i)g[i]g[i-1];for(intim;in;i)f[i]max(A,f[i])f[i-1];longlongans0;for(inti0;in;i)ansmax(ans,g[max(i-m1,0)]g[n]-g[i]f[i]-f[max(i-m,0)]);printf(%lld\n,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容