Vanya and Brackets 题解

题目传送门

一道枚举题。

枚举左括号和右括号的位置括号，为了答案最优，左括号只能在开头或者 * 的右边。右括号只能在末尾或者 * 的左边。每一次枚举都计算一下这个加了括号后表达式的值，最后取最大值即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
string s, backup1;
ll ans, cur;
ll facrot();
ll term();
ll expr();
ll factor() {
    ll res = 0;
    if (s[cur] == '(') {
        cur++;
        res = expr();
        cur++;
    }
    else {
        while (1) {
            if (s[cur] >= '0' and s[cur] <= '9') {
                res = (res * 10 + s[cur] - '0');
                cur++;
            }
            else break;
        }
    }
    return res;
}
ll term() {
    ll res = factor();
    while (1) {
        if (s[cur] == '*') {
            cur++;
            res = res * factor();
        }
        else if (s[cur] == '/') {
            cur++;
            res = res / factor();
        }
        else break;
    }
    return res;
}
ll expr() { // 表达式求值
    ll res = term();
    while (1) {
        if (s[cur] == '+') {
            cur++;
            res += term();
        }
        else if (s[cur] == '-') {
            cur++;
            res -= term();
        }
        else break;
    }
    return res;
} 
signed main() {
    ios :: sync_with_stdio(0);
    cin >> s;
    backup1 = s;
    for (ll i = 0; i < s.size(); i++) {
        if (s[i] == '*' or i == 0) {
            if (i != 0) s.insert(i + 1, "(", 0, 1);
            else s.insert(i, "(", 0, 1);
            string backup2 = s;
            for (ll j = i + 1; j < s.size(); j++) {
                if (s[j] == '*' or j == s.size() - 1) {
                    cur = 0;
                    if (j != s.size() - 1) s.insert(j, ")", 0, 1);
                    else s.insert(j + 1, ")", 0, 1);
                    ans = max(ans, expr());
                }
                s = backup2;
            }
        }
        s = backup1;
    }  
    cout << ans;
    return 0;
}