#192. Polygon

Polygon

题目描述

n 个带权顶点排成环。每个顶点前有一条标记为加法 t 或乘法 x 的边。先删去任意一条边,将环展开为链;随后任意选择相邻两个数,按它们之间边的运算符合并,直到剩下一个数。求最终数的最大值,并列出能达到该最大值的所有首次删边编号。

输入格式

第一行 n≤50;随后 n 行为运算符 t 或 x 以及一个整数,按环的顺序描述边及其后顶点。

输出格式

第一行最大值,第二行按递增顺序输出所有合法的首次删边编号。

样例输入

4
t -7 t 4 x 2 x 5

样例输出

33
1 2

题意整理;原题与输入输出格式对照。