かっこを追加[Baek Jun 16637]

かっこを追加

A.方法

演算子の優先度が同じで、左から計算する条件で括弧内に演算子が1つしかない条件なので、問題アクセスはDPでアクセスすべきだと思います.(制限時間も0.5秒まで短い)
dp[N]:N個の数値が与えられたときに括弧を付けることで得られる最大値を格納する配列.
mdp[N]:N個の数値が与えられたときに括弧を付けることで得られる最小値を格納する配列.
dp[n]は、次の3つに最大値を格納する必要があります.
計算

dp[N-1]とN番目の数字

dp[N−2]および(N,N−1の数値を計算する値)を計算する.

計算

mdp[N-2]と(N,N-1の数字を計算)->mdp[n−2]は負数(N,N−1)であり,計算は負数であり,2つの乗算は最大値に達することができる.

最初は3番の条件を考えず、間違えて質問の検索で知りました.

B.実施

C.コード

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;
#define ll long long
char fm[19];

// 최대값을 저장하는 배열.
vector<ll> dp;
// 최소값을 저장하는 배열.
vector<ll> mdp;

int T, N;

// 문자로 된 값과 연산자를 통해 계산하는 함수.
ll cal(ll a, ll b, char c) {
    ll ret = 0;
    switch(c) {
        case '+':
            ret = a + b;
            break;
        case '-':
            ret = a - b;
            break;
        case '*':
            ret = a * b;
            break;
        default:
            //cout << "NO!" << endl;
            break;
    }
    return ret;
}
void solver(int n) {

    if(n == 0) {
        dp.push_back(atoi(&fm[0]));
        mdp.push_back(atoi(&fm[0]));
    }
    else if(n == 1) {
        dp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
        mdp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
    }
    else {
        ll a = dp[dp.size() - 2];
        ll b = dp[dp.size() - 1];
        ll c = mdp[mdp.size() - 2];
        ll d = mdp[mdp.size() - 1];

        char oa = 2 * (n - 2) + 1;
        char ob = 2 * (n - 1) + 1;

        dp.push_back(max(cal(b, atoi(&fm[2 * n]), fm[ob]), cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
        dp[dp.size() - 1] = max(dp[dp.size() - 1], cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));

        mdp.push_back(min(cal(d, atoi(&fm[2 * n]), fm[ob]), cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
        mdp[dp.size() - 1] = min(mdp[mdp.size() - 1], cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));
    }

    if(N / 2 == n)
        return;
    else
        solver(n + 1);
}

int main() {
    //scanf("%d", &T);
    T = 1;
    for(int tc = 0; tc < T; tc++) {
        scanf("%d", &N);

        scanf("%s\n", fm);
        dp.clear();
        mdp.clear();
        solver(0);

        printf("%d\n", dp[dp.size() - 1]);
    }
    return 0;
}

D.結果