P9367 [ICPC2022 Xi'an R] Strange Sum 题解

· · 题解

题意：

给定一个序列 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 记录。