后缀表达式其实就是省略括号的普通运算,通过从左向右运算的顺序,替代括号的功能。
我们将它转换回来,其实就是有n个加号,m个减号,n+m+1个数,可以加括号,问组成表达式的最大值。
若只有正号,加上所有数即可。
若含有负号,考虑…+…-(…+…+…)的形式,我们想要加上一个数,既可以放在括号外,用+连接,又可以放在括号内,用-连接。想要减去一个数,同理。
所以,我们可以任意消耗加号或减号,使正数被加,负数被减。
由此可得,本式中有效符号只有一个负号,那这个负号减去最小值即可,并且括号外至少有一个数,那这个数填最大值即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200010;
typedef long long LL;
int a[N];
int n,m;
int main(){
cin>>n>>m;
LL res=0;
for(int i=0;i<n+m+1;i++) scanf("%d",&a[i]);
if(m==0){
for(int i=0;i<n+m+1;i++) res+=a[i];
}
else{
sort(a,a+n+m+1);
res=a[n+m]-a[0];
for(int i=1;i<n+m;i++) res+=abs(a[i]);
}
cout<<res;
return 0;
}