2187: 宝典2第十一章多边形魔法阵

【题目描述】多边形魔法阵(MagicArray.cpp/c/pas)IOI 98

多边形魔法阵启动规则是这样的：开始时有一个N个顶点的多边形。如图所示，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。

第一步，一条边被拿走；随后各步包括如下：

选择一条边E和连接着E的两个顶点V₁和 V₂；

得到一个新的顶点，标记为V₁与V₂通过边E上的运算符运算的结果。

最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。

请看图的样例：

写一个程序，对于给定一个多边形，计算出可能的最高得分。

【输入格式】

　　输入共两行，第一行一个整数n表示顶点个数，第二行共2×n个数，分别为数字和字符。例如：对于上图中的问题，我们可以这样按输入样例中的例子输入，数学中的“+”号代表加法，小写字母“x”代表乘法。

【输出格式】

　　一个整数，计算最高得分。

【输入样例】

　　5

　　10 + -1 x -2 x 3 + -8 x

【输出样例】

　　486