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

· · 题解

题意简述

给定长度为 n 的序列 a_i，选择若干元素（可以不选），求元素之和的最大值。需要满足若选择 a_i，则所有长度为 i 的子区间中最多只能选择 2 个元素。

解题思路

假设选择编号最大的元素为 a_x，那么在区间 [1,x] 中最多只能选择两个元素，因为序列中没有比 a_x 编号更大的元素。

因此，整个序列中最多只能选择两个元素，考虑三种情况的最大值即可：

  1. 不选择任何元素：0；
  2. 选择 1 个元素：\max_1；
  3. 选择 2 个元素：\max_1+\max_2。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int mx1=-inf,mx2=-inf;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(t>mx1){mx2=mx1;mx1=t;}
        else if(t>mx2){mx2=t;}
    }
    cout<<max({0,mx1,mx1+mx2})<<'\n';
    return 0;
}