A6999 | $[IOI 1998] Polygon$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Polygon 是一个玩家在一个有 $n$ 个顶点的多边形上玩的游戏，如图所示，其中 $n = 4$。每个顶点用整数标记，每个边用符号 + （加）或符号 * （乘积）标记。 第一步，删除其中一条边。随后每一步： 选择一条边连接的两个顶点 $V_1$ 和 $V_2$，用边上的运算符计算 $V_1$ 和 $V_2$ 得到的结果来替换这两个顶点。 游戏结束时，只有一个顶点，没有多余的边。 如图所示，玩家先移除编号为 $3$ 的边。之后，玩家选择计算编号为 $1$ 的边，然后计算编号为 $4$ 的边，最后，计算编号为 $2$ 的边。结果是 $0$。 （译者注：这里每条边的运算符旁边的数字为边的编号，不拿来计算） 编写一个程序，给定一个多边形，计算最高可能的分数。

输入描述一个有 $n$ 个顶点的多边形，它包含两行。第一行是数字 $n$，为总边数。 第二行描述这个多边形，一共有 $n$ 组，每组中第一个字符为边 $i$ 的计算符号（ t 代表相加， x 代表相乘），第二个代表顶点 $i$ 上的数字。多边形首尾相连。

第一行，输出最高的分数。在第二行，输出所有可能的在第一步即被清除后仍能得到最高分的边的下标，以严格升序输出。

输入 #1

4
t -7 t 4 x 2 x 5

输出 #1

33
1 2

C++ 编辑器

输入

输出