Preparing NOJ

多边形

1000ms 65536K

Description:

lqp家离学校十分十分远,没有人陪他玩,于是他只好自娱自乐了......

有这么一个N个顶点的多边形,每个顶点上标上一个数字,每条边上有一个运算符号+或者*,边从1到N编号。

游戏的规则是这样的:先去掉一条边,然后这样:每次选一条边e,它的两个端点是v1和v2,用一个新的顶点取代,顶点上的数是这两个数按e操作的结果。当只剩一个点的时候,游戏结束,得分就是你最后达到的那个数。

lqp很喜欢这个游戏,但是他不知道自己玩得如何,于是他想问你一个局面可以得到的最高分是多少,这样他好知道自己每次玩得如何。

Input:

输入描述N个顶点。有两行第一行是N3<=N<=20,2行按顺序给出运算符和数字中间全都用一个空格隔开。

Output:

最高得分。(保证答案在64位有符号整数范围内)

Sample Input:

4
+ -7 + 4 * 2 * 5 

Sample Output:

33

Note:

 

本题由旧版NOJ导入,来源:JSOI2010

Info

NOJ

Provider NOJ

Code NOJ1405

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet