1 //Accepted    244 KB    0 ms 2 //区间dp 3 //石子合并模型 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 const int imax_n = 105; 9 const int Pinf = 100000000;10 const int Ninf = -100000000;11 int dp_min[imax_n][imax_n];12 int dp_max[imax_n][imax_n];13 int a[imax_n];14 char s[imax_n][3];15 int n;16 int max(int a,int b)17 {18     return a>b?a:b;19 }20 int min(int a,int b)21 {22     return a<b?a:b;23 }24 int cal(int a,int b,char s[])25 {26     if (s[0]==‘t‘) return a+b;27     return a*b;28 }29 void Dp()30 {31     for (int i=1;i<2*n;i++)32     dp_max[i][i]=dp_min[i][i]=a[i];33     for (int l=2;l<=n;l++)34     {35         for (int i=1;i<2*n;i++)36         {37             int j=i+l-1;38             if (j>=2*n) break;39             dp_max[i][j]=Ninf;40             dp_min[i][j]=Pinf;41             for (int k=i;k<=j-1;k++)42             {43                 dp_max[i][j]=max(dp_max[i][j],cal(dp_max[i][k],dp_max[k+1][j],s[k+1]));44                 dp_max[i][j]=max(dp_max[i][j],cal(dp_min[i][k],dp_min[k+1][j],s[k+1]));45                 dp_min[i][j]=min(dp_min[i][j],cal(dp_min[i][k],dp_min[k+1][j],s[k+1]));46                 dp_min[i][j]=min(dp_min[i][j],cal(dp_max[i][k],dp_min[k+1][j],s[k+1]));47                 dp_min[i][j]=min(dp_min[i][j],cal(dp_min[i][k],dp_max[k+1][j],s[k+1]));48             }49         }50     }51     int ans=Ninf;52     for (int i=1;i<=n;i++)53     ans=max(ans,dp_max[i][i+n-1]);54     printf("%d\n",ans);55     int flag=0;56     for (int i=1;i<=n;i++)57     {58         if (dp_max[i][i+n-1]==ans)59         {60             if (flag==0)61             {62                 printf("%d",i);63                 flag=1;64             }65             else66             {67                 printf(" %d",i);68             }69         }70     }71     printf("\n");72 }73 int main()74 {75     while (scanf("%d",&n)!=EOF)76     {77         for (int i=1;i<=n;i++)78         scanf("%s%d",s[i],&a[i]);79         for (int i=1;i<n;i++)80         {81             a[n+i]=a[i];82             strcpy(s[n+i],s[i]);83         }84         Dp();85     }86     return 0;87 }