网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
多边形魔法阵
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 12:35 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 12:35 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 12:35 |
输入文件 | MagicArray.in | 输出文件 | MagicArray.out |
【题目描述】多边形魔法阵(MagicArray.cpp/c/pas)IOI 98
多边形魔法阵启动规则是这样的:开始时有一个N个顶点的多边形。如图所示,这里N=4。每个顶点有一个整数标记,每条边上有一个“+”号或“*”号。边从1编号到N。
第一步,一条边被拿走;随后各步包括如下:
选择一条边E和连接着E的两个顶点V1和 V2;
得到一个新的顶点,标记为V1与V2通过边E上的运算符运算的结果。
最后,游戏中没有边,游戏的得分为仅剩余的一个顶点的值。
请看图的样例:
写一个程序,对于给定一个多边形,计算出可能的最高得分。
【输入格式】
输入共两行,第一行一个整数n表示顶点个数,第二行共2×n个数,分别为数字和字符。例如:对于上图中的问题,我们可以这样按输入样例中的例子输入,数学中的“+”号代表加法,小写字母“x”代表乘法。
【输出格式】
一个整数,计算最高得分。
【输入样例】
5
10 + -1 x -2 x 3 + -8 x
【输出样例】
486