1503. [IOI 1998]多边形

【题目描述】

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

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

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

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

1、选出一条边 $E$，以及由 $E$ 联接的顶点 $V_1$ 和 $V_2$；

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

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

下面是一个游戏实例：

考虑图$1$中的多边形。

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

图$2$ 删除第 $3$ 条边

之后，玩家删除第 $1$ 条边

图$3$ 删除第 $1$ 条边

然后删除第 $4$ 条边，

图$4$ 删除第 $4$ 条边

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

图$5$ 删除第 $2$ 条边

任务：

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

【输入格式】

输入包含两行。

第一行为整数 $N$。

第二行用来描述多边形所有边上的符号以及所有顶点上的整数，从编号为 $1$ 的边开始，边、点、边…按顺序描述。

其中描述顶点即为输入顶点上的整数，描述边即为输入边上的符号，其中加号用 t 表示，乘号用 x 表示。

【输出格式】

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

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

【样例输入】

4
t -7 t 4 x 2 x 5

【样例输出】

33
1 2

【样例解释】

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

【数据范围与约定】

$1\leq N\leq 50$，且无论玩家如何操作，顶点上的数值均在 $[-32768, 32767]$ 之间。

【来源】

IOI1998 polygon

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