多边形（Polygon）

知识点

• 区间dp

题目描述

Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1 1 1, where N = 4 N = 4 N=4. Each vertex is labelled with an integer and each edge is labelled with either the symbol + + + (addition) or the symbol ∗ * ∗ (product). The edges are numbered from 1 1 1 to N N N.

On the first move, one of the edges is removed. Subsequent moves involve the following steps:

• Pick an edge E E E and the two vertices V 1 V1 V1 and V 2 V2 V2 that are linked by E E E.
• Replace them by a new vertex, labelled with the result of performing the operation indicated in E E E on the labels of V 1 V1 V1 and V 2 V2 V2.
• The game ends when there are no more edges, and its score is the label of the single vertex remaining.
  Consider the polygon of Figure 1 1 1. The player started by removing edge 3 3 3. After that, the player picked edge 1 1 1, then edge 4 4 4, and, finally, edge 2 2 2. The score is 0 0 0.
  
  Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.

输入格式

输出格式

样例

样例输入

样例输出

样例解释

数据范围