问题描述

给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？

请你输出这个最大的结果。

例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。

输出格式

输出一个整数，代表答案。

数据范围

0≤N,M≤105,

−109≤Ai≤109

输入样例：

1 1
1 2 3

输出样例：

4

思路

先来看看什么是后缀表达式，假设给定一个表达式 123+-，可以得到如下后缀树：

然后通过后序遍历进行计算，先计算 2+3=5，然后再和 1 进行减法运算得到 4。

科普完后，我们再进入正题，本题不能直接去将负号全给负数，正号全给正数，要考虑到有括号的情况，比如给定 3 个负号，那么不一定就是 a 1 − a 2 − a 3 − a 4 a_1-a_2-a_3-a_4a

1

−a

2

−a

3

−a

4

，假设加了个括号变成 a 1 − ( a 2 − a 3 − a 4 ) = a 1 − a 2 + a 3 + a 4 a_1-(a_2-a_3-a_4)=a_1-a_2+a_3+a_4a

1

−(a

2

−a

3

−a

4

)=a

1

−a

2

+a

3

+a

4

，所以给定 M 个负号，我们可以选定 1~M 个负号来使用。

解决掉这个问题后，我们来分情况进行讨论，现在有 N 个正号和 M 个负号：

1.如果 M=0，则直接将所有数都相加即可。

2.如果 M>0 且没有正号，则选择 1~M 个负号均可；如果 M>0 且有 N 个正号，则这个正号可以选择放到括号里变成负号，故可以选择 1~M+N 个负号。

所以负号是可以随意更改个数的，如果有负号，至少要保留一个，整理一下我们可以得到如下结论：

1.如果 M=0 ，则答案就是所有数相加。

2.如果 M>0 ，则我们至少要有一个负号，剩下负号可以选择留在这个负号的外面，也可以留在负号的里面，如果是负数，则将负号放到负数前面即可。所以至少存在一个最大值 b 和最小值 a（N>2），故可以得到 b − ( a + . . . ) + . . . b-(a+...)+...b−(a+...)+...，这样答案就是最大值减去这个最小值，然后再加上剩下所有数的绝对值。

举个例子，比如给定 N+M+1 个数，注意题目给定的全是整数，假设给定有 3 个正号和 1 个负号以及一个序列 {-1,-3,6,3,1}，则按照上面的操作进行：

1.由于负号数量大于 0 ，则需要找到其中最小值 -3 和最大值 6 。

2.所以答案就等于 res = 6 - (-3 + (-1)) + 3 + 1 = 6 - (-3) + 1 + 3 + 1 = 14。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int a[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    int k = n + m + 1;
    for (int i = 0; i < k; i++)    scanf("%d", &a[i]);
    LL res = 0;
    if (!m)  //全是正号
    {
        for (int i = 0; i < k; i++)    res += a[i];
    }
    else    //至少有一个负号
    {
        sort(a, a + k);    //排序，方便找最大最小值
        res = a[k - 1] - a[0];
        for (int i = 1; i < k - 1; i++)  res += abs(a[i]);
    }
    printf("%lld\n", res);
    return 0;
}