题目大意
给定一个多边形，对应节点上标记有一个数字，每条边上标记有加（t）或乘（x）表示相邻两个节点可进行的操作，操作后两个节点将合并为一个节点，首先删去一条边（不进行操作），之后在若干次操作后使得该多边形只剩一个节点，且要求所剩节点标记的数最大化，询问最大的数字
题目分析
如图是题目所给出的示例图，我们可以通过模拟该图来得到我们代码实现的过程。
Quest1：如何处理环？
我们先假定删除了某条边，注意这里第一步是删除，并没有进行操作。
然后我们就要一系列的合并操作，完成之后又要换另一条边删掉，继续下去。。。
很明显这是一个很暴力的算法，而对于这种环状的区间dp问题，大家应该能反应出来，我们可以通过破环成链的方法，具体的就是将原本的一个环在复制一遍，形成一个长度为原先二倍的大环，这个时候随便断哪一条边都没有问题了，所以我们下面的操作中默认断掉了第一条边，或者说是第一条输入的边。
Ques2：如何实现合并？
之后我们可以开始合并操作，在这道题中，我们应当能发现现在是对一条链进行的区间合并操作，很容易就想到区间dp，因此，我们会用到下述转移方程：
\[f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])
\]
不过与常规区间dp的不同之处也显而易见，我们的转移过程中不一定只涉及到加法这一操作，而对于乘法的处理，或许会想到：
\[f[i][j]=max(f[i][j],f[i][k]*f[k+1][j])
\]
似乎到这一步就已经大功告成了,于是我们自信满满的打出以下代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=-0x3f3f3f3f;
char op[100];
int dp[200][200];
int main(){cin >> n;memset(dp,-0x3f,sizeof dp);for(int i=1;i<=n;i++){cin >> op[i-1] >> dp[i][i];op[i+n-1]=op[i-1];dp[i+n][i+n]=dp[i][i];}for(int len=2;len<=n;len++)for(int l=1;l<=n;l++){int r=l+len-1;for(int k=l;k<r;k++){if(op[k]=='t') dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);if(op[k]=='x') dp[l][r]=max(dp[l][r],dp[l][k]*dp[k+1][r]);}}for(int l=1;l<=n;l++) ans=max(ans,dp[l][l+n-1]);cout << ans << '\n';for(int l=1;l<=n;l++) if(ans==dp[l][l+n-1]) cout << l << ' ';return 0;
}
