C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

char c[N];//操作符表示第i个点前面的操作符
int w[N];//数字
int dp_min[N][N], dp_max[N][N];
int n;

int main(){
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> c[i] >> w[i];
        c[i+n] = c[i];
        w[i+n] = w[i];
    }
    memset(dp_min, 0x3f, sizeof dp_min);
    memset(dp_max, -0x3f, sizeof dp_max);
    for(int len = 1;len <= n;++len)
        for(int l = 1;l + len - 1 <= 2*n;++l){
            int r = l + len - 1;
            if(len == 1){
                dp_min[l][r] = w[l];
                dp_max[l][r] = w[l];
            }else
                for(int k = l;k < r;++k){//这里注意下，K 不可以从l+1开始
                    char op = c[k+1];
                    int lmin = dp_min[l][k], lmax = dp_max[l][k];
                    int rmin = dp_min[k+1][r], rmax = dp_max[k+1][r];
                    if(op == 't'){
                        dp_min[l][r] = min(dp_min[l][r], lmin + rmin);
                        dp_max[l][r] = max(dp_max[l][r], lmax + rmax);
                    }else{
                        int x1 = lmin * rmin, x2 = lmin * rmax, x3 = lmax * rmax, x4 = lmax * rmin;
                        dp_min[l][r] = min(dp_min[l][r], min(min(x1, x2), min(x3, x4)));
                        dp_max[l][r] = max(dp_max[l][r], max(max(x1, x2), max(x3, x4)));
                    }
                }
        }

    int ans = -0x3f3f3f3f;
    for(int i = 1;i <= n;++i) ans = max(ans, dp_max[i][i+n-1]);
    cout << ans << endl;

    for(int i = 1;i <= n;++i)
        if(dp_max[i][i+n-1] == ans){
            cout << i << " ";
        }
}