題目描述

給定?N?個加號、M?個減號以及?N+M+1 個整數?A1,A2,???,AN+M+1?，小明想知道在所有由這N?個加號、M?個減號以及?N+M+1 個整數湊出的合法的 后綴表達式中，結果最大的是哪一個？

請你輸出這個最大的結果。

例如使用 1 2 3 + -，則 "2 3 + 1 -" 這個后綴表達式結果是 4，是最大的。

輸入描述

第一行包含兩個整數 N,M。

第二行包含?N+M+1 個整數?A1,A2,???,AN+M+1?。

其中，0≤N,M≤105，?≤Ai?≤。

輸出描述

輸出一個整，代表答案。

輸入輸出樣例

示例

輸入

1 1
1 2 3

輸出

4

中綴轉后綴的順序是固定的:

1. 轉換算法遵循明確的規則（如運算符優先級和結合性）

2. 使用棧結構保證了確定的處理順序

3. 結果后綴表達式能唯一反映原中綴表達式的運算順序

例如：(3 + 4) × 5 - 6?只能轉換為?3 4 + 5 × 6 -

后綴轉中綴的順序不固定:

1. 運算符優先級的影響：相同的后綴表達式可能對應不同括號位置的中綴表達式

   • 例如：3 4 + 5 ×?可轉為?(3 + 4) × 5?或?3 + 4 × 5（后者數學等價但括號位置不同）

2. 結合性的影響：相同優先級的運算符可能有不同分組方式

   • 例如：3 4 5 + +?可轉為?3 + (4 + 5)?或?(3 + 4) + 5

3. 交換律的影響：可交換運算符（如+、×）的操作數順序可以交換

   • 例如：2 3 ×?可轉為?2 × 3?或?3 × 2

后綴轉中綴中可以隨意加括號、交換運算符的順序

思路：

1.如果沒有減號，最大的結果就是n+m+1個數的和

2.?如果有減號：最終只有1個減號起作用，其他減號可以抵消

與負數匹配的減號——負負得正，相消

與負數匹配的加號——放到第一個減號里? ?

eg: -5,?-3, 1, 2, +, -, -? ? ? ? ?2 - ((-5)+(-3)) +1

與正數匹配的減號——放到第一個減號里

eg: 1, 2, 3, 5, -, -, -? ? ? ? ?5 - (1-2-3)

與正數匹配的加號——正好

所以，最后的結果就是最大數-最小數+其他數的絕對值

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int a[200010];
long long ans; //必須開long long int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, m; //加號、減號的個數 cin>>n>>m;int cnt=n+m+1;for(int i=1; i<=cnt; ++i) cin>>a[i];sort(a+1, a+cnt+1);//如果沒有減號 if(m==0){		for(int i=1; i<=cnt; ++i) ans += a[i];cout<<ans;return 0;		}ans = a[cnt]-a[1];for(int i=2; i<=cnt-1; ++i){ans += abs(a[i]);	}cout<<ans;return 0;
}