P8102 「LCOI2022」 Cow Insertion

题目背景

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

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 2 50
60 100 70

输出 #1

270

说明/提示

【样例解释】

• 当 Bessie 在第一个位置时（$50,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=260$。
• 当 Bessie 在第二个位置时（$60,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=260$。
• 当 Bessie 在第三个位置时（$60,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=270$。
• 当 Bessie 在第四个位置时（$60,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=270$。

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

【数据范围与约定】

对于 $100\%$ 的数据，$1\le m\le n$，$0\le a_i,A\le 100$。

C++实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long long f[5000010], a[5000010], g[5000010];
int q[5000010], st = 1, ed;
int main()
{
	int n, m;
	long long A;
	scanf("%d%d%lld", &n, &m, &A);
	long long sum = A;
	for (int i = 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);
		return 0;
	} // 特判
	st = 1, ed = 0;
	for (int i = 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 (int i = m + 1; i <= n; i++) g[i] += g[i - 1];
	for (int i = m; i <= n; i++)
		f[i] = max(A, f[i]) + f[i - 1];
	long long ans = 0;
	for (int i = 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);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容