多边形游戏

【题目描述】 lqp家离学校十分十分远，没有人陪他玩，于是他只好自娱自乐了…… 有这么一个N个顶点的多边形，每个顶点上标上一个数字，每条边上有一个运算符号+或者*，边从1到N编号。 游戏的规则是这样的:先去掉一条边，然后这样：每次选一条边e，它的两个端点是v1和v2，用一个新的顶点取代，顶点上的数是这两个数按e操作的结果。当只剩一个点的时候，游戏结束，得分就是你最后达到的那个数。 lqp很喜欢这个游戏,但是他不知道自己玩得如何,于是他想问你一个局面可以得到的最高分是多少,这样他好知道自己每次玩得如何。 【输入格式】 输入描述N个顶点。有两行，第一行是N（3<=N<=20）,第2行按顺序给出运算符和数字，中间全都用一个空格隔开。 【输出格式】 最高得分。 【样例输入】 4 + -7 + 4 * 2 * 5 【样例输出】 33 【分析】 首先理解下样例： 如图，4*2*5-7=33。 设num[i]存放多边形顶点的数，op[i]存放多边形边上的运算符，f[i][j][0..1]存放合并点i到点j的最小值和最大值。 考虑多边形的最后一次合并，令其发生在点i+x处则可以将链(i,j)分割成(i,x)和(i+x,j-x)两段，我们可以将两个子链的最大值和最小值算出来，存在四个变量a,b,c,d中。 注意：i+x的值可能超过n，需要取模！ 此时对op[i+x]分类讨论： 当op[i+x]为加号时，e=a+b,i=c+b,g=a+d,h=c+d； 当op[i+x]为乘号时，e=a*b,i=c*b,g=a*d,h=c*d. 最后计算f[i][j][0..1]的值即可。