本题解同步发布于我的博客 。

思路

后缀表达式有什么不同？其实就是相当于能对原表达式加任意个括号来改变运算顺序。
1. 对于加号来说，加不加括号都没用，所以可以特判一下全部是加号的情况。
2. 对于减号来说，若给了n个加号，m个减号，n+m+1个数，那么表达式中减号的个数经过加括号处理再去掉括号变号后，实际的减号数可为1~n+m（至少有1个）

为了求表达式运算结果的最大值，考虑处理方式：无论给了多少个减号，我们经过加括号处理，都能把最终的表达式变成只剩下1个减号！

为了方便表述，设正数之和为sum_po，正数集合中最小数为mi_po，负数之和为sum_ne，负数集合中绝对值最小的负数为mi_ne，分3种情况讨论：
1. 所有数为正数，$ans=sum\_po-2\*mi\_po$
2. 所有数为负数，$ans=-sum\_ne+2*mi\_ne$
3. 既有正数也有负数，$ans=sum\_po-sum\_ne$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x;
vector<int>po,ne; // store positive and negative numbers
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    ll sum_po=0,sum_ne=0;
    for(int i=1;i<=n+m+1;i++)
    {
        cin>>x;
        if(x>=0)
        {
            po.push_back(x);
            sum_po+=x;
        }
        else
        {
            ne.push_back(x);
            sum_ne+=x;
        }
    }
    if(m==0)printf("%lld\n",sum_po+sum_ne); // all symbols are '+'
    else // NOTE: m>=1
    {
        sort(po.begin(),po.end(),greater<int>());
        sort(ne.begin(),ne.end());  
        ll ans=0;
        if(po.size()&&ne.size()) // 既有正数也有负数
        {
            ans=sum_po-sum_ne;
        }
        else if(po.size()&&!ne.size()) // 所有数为正数
        {
            ans=sum_po-2*po[po.size()-1];
        }
        else // !po.size()&&ne.size() // 所有数为负数
        {
            ans=-sum_ne+2*ne[ne.size()-1];
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
10 10
79 -84 56 51 -13 -1 38 -82 -99 15 -21 -67 7 -73 -43 97 94 80 90 76 -31
ans:1197

10 10
-90 34 -52 85 -37 -82 -11 -5 -78 -56 -4 78 -39 -97 -68 -44 -64 100 -48 33 9
ans:1114

4 1
-1 -2 -3 -4 -5 -6
ans:19

1 1
1 2 3
ans:4
*/

这题数据点很坑啊…我wa了好多次…