/ Vijos / 题库 /

多边形

多边形

描述

zgx给了你一个n边的多边形,这个多边形每个顶点赋予一个值,每条边都被标上运算符号+或*,对于这个多边形有一个游戏,游戏的步骤如下:
(1)第一步,删掉一条边;
(2)接下来n-1步,每步对剩下的边中的一条进行操作,用一个新的顶点取代这条边。将这条被取代的边两端的顶点的整数值通过边上的运算得到的结果赋予新顶点。

最后,所有的边被删除,只剩一个定点,这个定点的整数值就是游戏的最后得分。

你要做的就是算出给你的多边形能得到的最高分和最低分。

格式

输入格式

第一行,n;
第二行,n条边的运算符;
第三行,n个顶点的初始值;

注:边和顶点都是按顺序输入,
第一个输入的边连接第一个输入的第二个输入的顶点。

输出格式

最大值;
最小值。

样例1

样例输入1

4
+++*
1 1 1 1

样例输出1

4
3

限制

各个测试点2s

提示

n<=50
解释样例:

  1
 + +
1   1
 * +
  1

最大值:1+1+1+1=4或(1+1)*(1+1);
最小值:1*1+1+1=3;

信息

ID
1565
难度
7
分类
动态规划 | 环形DP 点击显示
标签
递交数
1657
已通过
299
通过率
18%
上传者