OpenJudge

b:多边形游戏

总时间限制:
1000ms
内存限制:
65536kB
描述
  一个多边形,开始有n个顶点。每个顶点被赋予一个正整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
    现在来玩一个游戏,该游戏共有n步:
    第1步,选择一条边,将其删除
    随后n-1步,每一步都按以下方式操作:(1)选择一条边E以及由E连接着的2个顶点v1和v2; (2)用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2,将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。

    最后,所有边都被删除,只剩一个顶点,游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少?
输入
第一行为多边形的顶点数n(n ≤ 20),其后有n行,每行为一个整数和一个字符,整数为顶点上的正整数值,字符为该顶点到下一个顶点间连边上的运算符“+”或“*”(最后一个字符为最后一个顶点到第一个顶点间连边上的运算符)。
输出
输出仅一个整数,即游戏所计算出的最大值。
样例输入
4
4 *
5 +
5 +
3 +
样例输出
70
提示
小规模问题可不必用动态规划方法编程求解,仅用递归就可以求解。
计算中不必考虑计算结果超出整数表达范围的问题,给出的数据能保证计算结果的有效性。
在给的例子中,计算过程为(3+4)*(5+5)=70。
全局题号
6258
提交次数
5
尝试人数
2
通过人数
1