易错点：
- 由于需要在一开始减少一条边且相邻输入数据在图上相邻，需要将输入的运算符复制一倍后向左平移一个单位.
- 乘法的状态转移需要注意负负得正，也就是说，最大值可以由两个最小值推导出来。因此，需要保存最小值，也就是使用f[l][r][0/1]分别保存最大/最小值。而最小值也有可能由多种情况推导出来，因此如果拿不准可以四种情况都尝试进行转移.
- 输出答案时不能直接输出f[1][n][0]，因为题目需要断环并加一倍在后面.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=120,INF=1<<30;
int f[MAXN][MAXN][2];
char opt[MAXN];
int a[MAXN];
int main(){
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++){
f[i][j][0]=-INF;
f[i][j][1]=INF;
}
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
char nowOpt;int nowValue;
cin>>nowOpt>>nowValue;
opt[i]=opt[i+n]=nowOpt;
a[i]=a[i+n]=nowValue;
f[i][i][0]=f[i][i][1]=a[i];
f[i+n][i+n][0]=f[i+n][i+n][1]=a[i];
}
for(int i=1;i<2*n;i++)
opt[i]=opt[i+1];
for(int len=2;len<=n;len++){
for(int l=1;l<=2*n-len+1;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
char nowOpt=opt[k];
if(nowOpt=='t'){
f[l][r][0]=max(f[l][r][0],f[l][k][0]+f[k+1][r][0]);
f[l][r][1]=min(f[l][r][1],f[l][k][1]+f[k+1][r][1]);
}else{
f[l][r][0]=max(f[l][r][0],f[l][k][0]*f[k+1][r][0]);
f[l][r][0]=max(f[l][r][0],f[l][k][1]*f[k+1][r][1]);
f[l][r][1]=min(f[l][r][1],f[l][k][1]*f[k+1][r][0]);
f[l][r][1]=min(f[l][r][1],f[l][k][0]*f[k+1][r][1]);
}
}
}
}
int nowAns=-INF;
vector<int> scc;
for(int i=1;i<=n;i++){
if(f[i][i+n-1][0]>nowAns){
scc.clear();
scc.push_back(i);
nowAns=f[i][i+n-1][0];
}else if(f[i][i+n-1][0]==nowAns){
scc.push_back(i);
}
}
cout<<nowAns<<endl;
for(int i=0;i<scc.size();i++){
int nowValue=scc.at(i);
cout<<nowValue<<" ";
}
cout<<endl;
return 0;
}