60pts求调

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 110;
const int INF = 1e18;

int a[N], mx[N][N], vis[N][N], mn[N][N];
int n;
char s[N];
vector<int> res;

void dfs(int l, int r){
	if(vis[l][r]) return ;
	if(l == r){
		return mx[l][r] = mn[l][r] = a[l], void();	
	}
	vis[l][r] = 1;
	mx[l][r] = -INF;
	mn[l][r] = INF;
	for(int i = l; i < r; ++i){
		dfs(l, i), dfs(i + 1, r);
		if(s[i + 1] == 't'){
			mx[l][r] = max(mx[l][r], mx[l][i] + mx[i + 1][r]);
			mn[l][r] = min(mn[l][r], mn[l][i] + mn[i + 1][r]);
		}else{
			mx[l][r] = max(mx[l][r], max(mx[l][i] * mx[i + 1][r], mn[l][i] * mn[i + 1][r]));
			mx[l][r] = max(mx[l][r], max(mx[l][i] * mn[i + 1][r], mn[l][i] * mx[i + 1][r]));
			mn[l][r] = min(mn[l][r], min(mx[l][i] * mx[i + 1][r], mn[l][i] * mn[i + 1][r]));
			mn[l][r] = min(mn[l][r], min(mx[l][r] * mn[i + 1][r], mn[l][i] * mx[i + 1][r]));
		}
	}
}

signed main(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> s[i] >> a[i];
		s[n + i] = s[i], a[n + i] = a[i];	
	}
	dfs(1, n << 1);
	int ans = -INF;
	for(int i = 1; i <= n; ++i){
		if(mx[i][i + n - 1] > ans){
			ans = mx[i][i + n -1];
			res.resize(0);
		}
		if(mx[i][i + n -1] == ans)
			res.push_back(i);
	}
	cout << ans << '\n';
	for(auto x : res)
		cout << x << ' ';
	return 0;	
}