题目描述

blablabla

样例

blablabla

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50 + 10;
int w[2 * maxn];
char oper[2 * maxn];
int f[2 * maxn][2 * maxn], g[2 * maxn][2 * maxn];
int getmax(int a, int b, int c, int d) {
    int aa = max(a, b), aaa = max(c, d);
    return max(aa, aaa);
}
int getmin(int a, int b, int c, int d) {
    int aa = min(a, b), aaa = min(c, d);
    return min(aa, aaa);
}
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= 2 * n; i ++) {
        if(i % 2 == 1) {
            cin >> oper[i / 2 + 1];
            oper[i / 2 + 1 + n] = oper[i / 2 + 1];
        }
        else {
            cin >> w[i / 2];
            w[i / 2 + n] = w[i / 2];
        }
    }
    for(int len = 1; len <= n; len ++) {
        for(int i = 1; i + len - 1 <= 2 * n; i ++) {
            int j = i + len - 1;
            if(len == 1) {
                f[i][j] = w[i];
                g[i][j] = w[i];
                continue;
            }
            f[i][j] = -0x3f3f3f3f, g[i][j] = 0x3f3f3f3f;
            for(int k = i; k < j; k ++) {
                if(oper[k + 1] == 't') {// before is +
                    f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
                    g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);
                    //cout << i << " " << j << " " << f[i][j] << endl;
                }
                else if(oper[k + 1] == 'x') {
                    int a = f[i][k], b = f[k + 1][j];
                    int c = g[i][k], d = g[k + 1][j];
                    int ab = a * b, ad = a * d, cb = c * b, cd = c * d;// miss before
                    f[i][j] = max(f[i][j], getmax(ab, ad, cb, cd));// before is a, b, c, d;
                    g[i][j] = min(g[i][j], getmin(ab, ad, cb, cd));
                    //cout << i << " " << j << " " << f[i][j] << endl;
                }
            }
        }
    }
    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++)
        res = max(res, f[i][i + n - 1]);
    cout << res << endl;
    for(int i = 1; i <= n; i ++) {
        if(f[i][i + n - 1] == res) 
            cout << i << " ";
    }
    return 0;
}