一道稍微变型的区间DP模版，由于可能出现负数，那么最小值*最小值有可能变为最大值，因此需要记录一下最大值和最小值，再考虑状态的转移，删边就复制多一串就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N=105;
int f[2][N][N],a[N];char c[N];//0 max 1 min
int main()
{
    int n;scanf("%d",&n);
    memset(f[0],0xcf,sizeof(f[0]));
    memset(f[1],0x3f,sizeof(f[1]));
    for(int i=1;i<=n;i++)cin>>c[i],scanf("%d",&a[i]),c[i+n]=c[i],a[i+n]=a[i],f[1][i][i]=f[0][i][i]=f[1][i+n][i+n]=f[0][i+n][i+n]=a[i];
    for(int k=2;k<=n;k++)
        for(int l=1;l<=2*n-k+1;l++)
        {
            int r=l+k-1;
            for(int mid=l+1;mid<=r;mid++)
                if(c[mid]=='t')
                {
                    f[0][l][r]=max(f[0][l][r],f[0][l][mid-1]+f[0][mid][r]);
                    f[1][l][r]=min(f[1][l][r],f[1][l][mid-1]+f[1][mid][r]);
                }
                else
                {
                    f[0][l][r]=max(f[0][l][r],max(f[0][l][mid-1]*f[0][mid][r],f[1][l][mid-1]*f[1][mid][r]));
                    f[1][l][r]=min(f[1][l][r],min(f[0][l][mid-1]*f[0][mid][r],min(f[0][l][mid-1]*f[1][mid][r],min(f[1][l][mid-1]*f[0][mid][r],f[1][l][mid-1]*f[1][mid][r]))));
                }
        }
    int ans=0xcfcfcfcf;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[0][i][i+n-1]);
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)if(f[0][i][i+n-1]==ans)printf("%d ",i);
    puts("");
    return 0;
}