OI题库

【题目描述】

多边形(Polygon)游戏是单人玩的游戏，开始的时候给定一个由N个顶点构成的多边形(图1所示的例子中，N=4)，每个顶点被赋予一个整数值，而每条边则被赋予一个符号：+(加法运算)或者*(乘法运算)，所有边依次用整数1到N标识。

图1一个多边形的图形表示

首次移动(first move)，允许将某条边删除；

接下来的每次顺序移动(subsequentmoves)，包括下面步骤：

1、选出一条边E，以及由E联接的顶点V1和V2；

2、用一个新的顶点，取代边E及其所联接的两个顶点V1和V2。新顶点要赋予新的值，这个值是对V1和V2，做由E所指定的运算，所得到的结果。

所有边都被删除后，只剩下一个顶点，游戏结束。游戏的得分就是该顶点的数值。

下面是一个游戏实例：

考虑图1中的多边形。

玩家第一步删除第3条边。结果如图2所示。

图2 删除第3条边

之后，玩家删除第1条边

图3 删除第1条边

然后删除第4条边，

图4 删除第4条边

最后删除第2条边。得分是0.

图5 删除第2条边

任务：

编写一个程序，对于任意给定的多边形，计算可能的最高得分，并且列举出所有的可以导致最高得分的被首次移动的边。

【输入格式】

文件POLYGON.IN给出的是，由N个顶点构成的多边形。文件包括2行：

第一行记录的是数值N；

第二行包含所有边(1，…，N)分别被赋予的符号，以及嵌入到两条边之间的顶点的数值(第一个整数值对应于与1号、2号边同时相连的顶点；第二个整数对应于与2号、3号边同时相连的顶点；…；等等。最后一个数值对应于与N号、1号边同时相连的顶点)，符号和数值之间由一个空格分隔。边的符号有2种：字母t(对应于+)，字母x(对应于*)。

【输出格式】

在文件POLYGON.OUT的第一行，你的程序必须输出在输入文件指定条件下可能得到的最高得分。

有些边如果在首次移动中被删除，可以导致最高得分。在输出文件的第二行，要求列举出所有这样的边，而且按照升序输出，其间用一个空格分开。

【样例输入】

4

t -7 t 4 x 2 x 5

【样例输出】

33

1 2

【提示】

样例输入对应于图1所示的多边形。第二行的第一个字符是1号边的符号。

【来源】

IOI1998 polygon

翻译 by 来煜坤，《把握本质，灵活运用——动态规划的深入探讨》