给定N个顶点的多边形，每个顶点标有一个整数，每条边上标有+(加)或是×(乘)号，并且N条边按照顺时针
依次编号为1~N。下图给出了一个N＝4个顶点的多边形。
游戏规则 ：(1) 首先，移走一条边。 (2) 然后进行下面的操作： 选中一条边E，该边有两个相邻的顶点，不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算，得到一个整数；用该整数标注一个新顶点，该顶点代替V1和V2 。 持续进行此操作，直到最后没有边存在，即只剩下一个顶点。该顶点的整数称为此次游戏的得分(Score)。
思路：
环状的用两倍的数组储存，删掉一条边后转换成去给一个式子加括号，怎么加使值最大。
状态转移方程:dp[i][j]=max(dp[i][j],d(i,k)$d(k+1,j));
$表示与k+1之间的运算符，i<=k<j.
样例输入:5 3*5+6+-7*3+
样例输出:78
代码：
#include<bits/stdc++.h> #define INF -9999999 using namespace std; const int maxn = 100; int num[maxn]; char s[maxn]; int dp[maxn][maxn]; int d(int i,int j){ if(dp[i][j]!=INF) return dp[i][j]; if(i==j) return dp[i][j]=num[i]; for(int k=i;k<j;k++){ if(s[k]=='*') dp[i][j]=max(dp[i][j],d(i,k)*d(k+1,j)); else dp[i][j]=max(dp[i][j],d(i,k)+d(k+1,j)); } return dp[i][j]; } int main() { int n; while(cin>>n&&n){ for(int i=0;i<n;i++){ cin>>num[i]; num[i+n]=num[i]; cin>>s[i]; s[i+n]=s[i]; } int ans=INF; fill(dp[0],dp[0]+maxn*maxn,INF); for(int i=0;i<n;i++){ ans=max(ans,d(i+1,i+n)); } cout<<ans<<endl; } return 0; }
