最值序列

解题思路

给一个长度为 n 的序列 a，一开始有一个数 A = 0，每次可以从序列中选一个数 b，令 A = A + b 或者 A = A * b，每个数都要使用一次，加的次数要和乘的次数相同，要求最大化 A，输出 A 对 998244353 取模的值。

对序列 a 进行排序，将前 n/2 个数相加，再依次乘以后面 n/2 个数。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int mod = 998244353;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];
    sort(a.begin(), a.end());
    long long A = 0;
    for(int i=0; i<n/2; ++i)
        A += a[i];
    A %= mod;
    for(int i=n/2; i<n; ++i){
        A *= a[i];
        A %= mod;
    }
    cout << A << endl;
    return 0;
}