2306: 蓝桥杯2019年第十届真题-后缀表达式

解题思路:其实就是使用n个加号和m个减号，可以随意使用括号，来使表达式的结果最大化。

              分情况讨论

              若 m == 0 ，只能全部求和

              若 m != 0 ，则再分----没有负数：最小的数前面是减号，其余数前面是加号

                                            ----有正数也有负数：整数前面是加号，负数前面是减号

                                           -----只有符数：取一个最大的数放在第一个位置，其余的数前面都是减号
 
注意事项:一个减号分配到k个数全加的括号中，去掉括号就变成了k个减号，一个减号分配到k个数全减的括号中，去括号就变成了一个减号和k-1个加号。

参考代码:

#include <bits/stdc++.h>

using namespace std;

int n, m;

int main()
{
    cin >> n >> m;
    int Max_a = -1e9 - 2, Min_a = 1e9 + 2;
    vector<int> a(n + m + 1);
    for (int i = 0; i < n + m + 1; ++i) {
        cin >> a[i];
        Max_a = max(Max_a, a[i]);
        Min_a = min(Min_a, a[i]);
    }
    long long ans = 0;
    for (auto it = a.begin(); it != a.end(); ++it) ans += *it;
    if (m != 0) {
        if (Min_a >= 0) {
            ans -= Min_a * 2;
        }
        else {
            ans = 0;
            for (auto it = a.begin(); it != a.end(); ++it) ans += abs(*it);
            if (Max_a < 0) {
                ans += Max_a * 2;
            }
        }
    }
    cout << ans << endl;
    return 0;
}