【题目大意】

给一个n边形，每个顶点上有一个数值，每条边上有一个运算符号。每次删去一条边，同时将这条边连接的两端点的数值进行运算(运算符号记为这条边上的符号)，求删去所有边后的最大值。

【思路分析】

首先断环为链，然后就跟是差不多的了，不过因为涉及到乘法并且有负数，所以DP过程中除了记录最大值还要记录最小值，详见代码。

【代码实现】

1 #include
      
        2 #include
       
         3 #define rg register 4 #define go(i,a,b) for(rg int i=a;i<=b;i++) 5 using namespace std; 6 const int N=102; 7 const int INF=1e9+9; 8 int n,m,a[N],f[N][N],g[N][N],ans=-INF; 9 char b[N];10 int main(){11     scanf("%d",&n);m=n<<1;12     go(i,1,n) {cin>>b[i]>>a[i];b[i+n]=b[i];a[i+n]=a[i];}13     go(i,1,m) go(j,1,m) f[i][j]=-INF,g[i][j]=INF;14     go(i,1,m) f[i][i]=g[i][i]=a[i];15     go(len,2,n)16         go(l,1,m-len+1)17     {18         int r=l+len-1;19         go(mid,l,r-1)20         {21             if(b[mid+1]=='t')22             {23                 f[l][r]=max(f[l][r],f[l][mid]+f[mid+1][r]);24                 g[l][r]=min(g[l][r],g[l][mid]+g[mid+1][r]);25             }26             else27             {28                 f[l][r]=max(f[l][r],max(f[l][mid]*f[mid+1][r],max(f[l][mid]*g[mid+1][r],max(g[l][mid]*f[mid+1][r],g[l][mid]*g[mid+1][r]))));29                 g[l][r]=min(g[l][r],min(f[l][mid]*f[mid+1][r],min(f[l][mid]*g[mid+1][r],min(g[l][mid]*f[mid+1][r],g[l][mid]*g[mid+1][r]))));30             }31         }32     }33     go(i,1,n) ans=max(ans,f[i][i+n-1]);34     printf("%d\n",ans);35     go(i,1,n) if(f[i][i+n-1]==ans) printf("%d ",i);36     return 0;37 }