自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:47:43，当前版本为作者最后更新于2023-05-23 22:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

给定一个序列 $a_1, a_2, \ldots, a_n$。

你需要从中选出若干个元素，使得：如果你选了 $a_i$，则对于任意长度为 $i$ 的区间（即 $a[j,j+i-1]$，其中 $1\le j\le n-i+1$），至多选 $2$ 个元素。

求出所选元素的最大和。

题解：

假设选了 $a_{i}$，那么 $a[1,i]$ 应当只有至多两个元素。

假设我们一共选了三个（或更多）元素，它们分别是 $a_x,a_y,a_z$，那么因为 $a[1,z]$ 只能有两个元素被选取，导致矛盾。

所以至多只能选两个元素。

排序一下，选取最大的那两个元素（如果非负的话），相加就是答案。

#include<bits/stdc++.h>
using namespace std;
int a[542457];
int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<max(0,a[n-2])+max(0,a[n-1]);//max(0,x)，即当x>0时取x（表示选取这个数），否则是0（不选择x这个数）
	return 0;
}

AC 记录。