本文主要是介绍AcWing 1247.后缀表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：贪心
由题目中我们可以知道，我们需要计算的是一个后缀表达式，要求尽可能的运算出最大的数。它给了我们加号和负号，让我们自己安排需要怎么做。
其实这里涉及到一个小学的知识点，也就是在括号遇到负号的时候，里面的符号需要发生必要的变化。如果括号前面有负号，那么括号里面的负号需要变成加号，而加号需要变成负号。
那么我们可以灵活运用这个性质，因为题目中并没有说括号的事情，实际上，我们在计算后缀表达式转化成我们的运算规则的时候就已经不自觉的加上括号了。所以，这里需要考虑我们本应该忽略的括号。
那么，我们也都知道，肯定是尽可能的加起来正数，减去负数，这样才能保证最后的结果是最大的。这个方向是对的，我们就往这个方向靠近。
首先想到的就是把这里面的数从小到大排序出来，然后，我们从尾一直加。但是，这样的话负号会怎么办呢？我们就换算成这样的形式：（..+...+..)-(...-..-..)如果把负号用在后者这样的括号里面，是不是就很nice？对的，我们就是这样把尽可能多的负号往里面加的。所以，去掉括号也就是相当于加上他们了。详细的图解可以看这位大佬的：AcWing 1247. 后缀表达式+思维图解 - AcWing
既然我们去掉括号之后，必定会有一个减去的数，那么这个数我们就可以让它是最小的数，减去最小的数，所得的结果才尽可能的大，所以我们首先用最大数减去最小数。然后逐一加上他们的绝对值（因为去掉括号之后就变号了，这个数是负数，你就减去负数，是正数你就加它，所以无论如何都i是绝对值，也就是不为负数）。
上代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 550
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
char maps[MAX][MAX];
int dist[MAX][MAX];
int a, b;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
int arr[200010];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;for (int i = 0; i < n+m+1; i++) {cin >> arr[i];}int sum = 0;sort(arr, arr + n + m + 1);if (!m) {for (int i = 0; i < n+m+1; i++) {sum += arr[i];}}else {sum += arr[n + m] - arr[0];for (int i = 1; i < m + n; i++) {sum += abs(arr[i]);}}cout << sum;return 0;
}这篇关于AcWing 1247.后缀表达式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
