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

· · 题解

题意简述

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

解题思路

假设选择编号最大的元素为 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 max1=-inf,max2=-inf;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        if(t>max1)
        {
            max2=max1;
            max1=t;
        }
        else if(t>max2)
        {
            max2=t;
        }
    }
    cout<<max(0,max(max1,max1+max2))<<'\n';
    return 0;
}