实际上就是枚举所有区间，求出所有区间可以获得的最大值和最小值，区间L的的结果可以由区间L-1的结果组合得到。
这题有一个小技巧很好用，就是求第i个结点顺时针向后的第t个结点如果是node(i,t)的话，那么node (i,t+1)的标号可以由
((i+t)%n )+1得到，实际上lebel[node(i,t)]=((i+t-1)%n )+1;所以这题结点从1开始存似乎更加便于计算。
//coded by abilitytao
//2010年6月1日17:25:38
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100;
int n;
int fmax[maxn][maxn];
int fmin[maxn][maxn];
int v[maxn];
int op[maxn];
void init()//初始化
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
fmax[i][j]=-999999999;
fmin[i][j]=999999999;
}
for(int i=1;i<=n;i++)
fmax[i][0]=fmin[i][0]=v[i];
}
void input()
{
scanf("%d",&n);
cin.ignore();
int i;
for(i=1;i<=n;i++)
{
char tem[10];
scanf("%s",tem);
if(tem[0]=='t')
op[i]=0;//0代表+号
else
op[i]=1;//1代表乘号
scanf("%d",&v[i]);
}
}
void solve()//DP过程
{
int mm=-999999999;
int i,t,L;
for(L=1;L<=n-1;L++)
{
for(i=1;i<=n;i++)
{
for(t=0;t<=L-1;t++)
{
if(op[(i+t)%n+1]==0)
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]+fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]+fmax[(i+t)%n+1][L-t-1]);
}
else
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
}
}
}
}
for(i=1;i<=n;i++)
if(fmax[i][n-1]>mm)
mm=fmax[i][n-1];
printf("%d\n",mm);
for(i=1;i<=n;i++)
if(fmax[i][n-1]==mm)
printf("%d ",i);
printf("\n");
}
int main()
{
input();
init();
solve();
return 0;
}