多边形游戏

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

    给定N(2<=N<=100)个顶点的多边形,每个顶点标有一个整数,每条边上标有+()或是×()号,并且N条边按照顺时针依次编号为1~N。下图给出了一个N4个顶点的多边形。

游戏规则

(1) 首先,移走一条边。

(2) 然后进行下面的操作:

选中一条边E,该边有两个相邻的顶点,不妨称为V1V2。对V1V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算,得到一个整数;用该整数标注一个新顶点,该顶点代替V1V2 。持续进行此操作,直到最后没有边存在,即只剩下一个顶点。该顶点的整数称为此次游戏的得分(Score)

任务:给定一个多边形,顶点和边已按上述方式进行标注。问:按照游戏规则,最高得分(最优值)是多少?对应该最高得分,按照什么顺序移走边(最优解)

下图对应的输入为:

4

t        -7      t        4       x       2       x       5

 

Input

含多个测试用例 第一行为测试用例个数t 下面是t组用例 每个用例有两行: 第一行是一个整数N 第二行按照 边顶点边顶点…边顶点 的顺序以此存放了N个顶点和N条边的标注信息。其中字符t表示+,字符x表示×。

Output

每个用例输出两行数据: 第一行是该游戏可能的最高得分。 第二行列出第一次移走哪条边(可能有多个, 如果是多个,则按照递增顺序排列),会导致最高得分的出现。

Sample Input

1
4
t	-7	t	4	x	2	x	5

Sample Output

33
1 2

Hint

Source

bingbing

提交代码