我在考虑以下问题的算法（在carrercup上找到）：
给定一个具有N个顶点和N条边的多边形。每个顶点上都有一个int数值（可以是负数），每条边上都有一个集合中的操作（*，+）。每次从多边形中删除边E时，将由该边连接的两个顶点（V1，V2）合并成一个新的顶点，并使用以下公式计算其值：V1 op(E) V2。最后一种情况是两个带有两条边的顶点，则结果是更大的那个。 返回给定多边形可以获得的最大结果值。
我认为我们可以采用贪心方法。即对于具有k条边的多边形，找到一个产生最大数字的配对（p，q）：（p，q）= max（{i操作j：i，j-相邻边}）
然后只需在多边形上调用递归： 1. 让函数CollapseMaxPair（P（k）） - 获取具有k条边的多边形并返回具有k-1条边的“折叠”多边形 2. 然后我们的递归：
P = P(N);
Releat until two edges left
P = CollapseMaxPair( P )
maxvalue = max ( two remained values)
你认为呢？
6+1 * 2 变成(6+1)*2比6+(1*2)大。*或+。我们的方法如下，我们将观察子问题F(i,j)，它表示a1,...aj的最大公式（括号化后）。我们将创建这些子问题的表，并观察到F(1,n)正好是我们要寻找的结果。F(i,j)
- If i>j return 0 //no sub-formula of negative length
- If i=j return ai // the maximal formula for one number is the number
- If i<j return the maximal value for all m between i (including) and j (not included) of:
F(i,m) (o(m)) F(m+1,j) //check all places for possible parenthasis insertion
A (-1) ------ B (-1)
| |
| |
| |
| |
D(1000000) ---C (-1)
显然，最好的策略是先将 (A,B) 合并，再合并 (B,C)，这样就可以得到单独的 D。不过你的算法会从 (A,D) 或者 (D,C) 开始，这样不是最优的。
贪心算法结合最小和也有类似的弱点，所以我们需要考虑其他方案。
我开始明白我们想要将所有正数放在一边，所有负数放在另一边。
如果我们将初始多边形看做一个状态，那么我们可以想象所有可能的子状态是折叠边缘后的图像。这样就创建了一个树形结构。广度优先搜索或深度优先搜索最终会给我们提供最优解，但最坏情况下需要遍历整个树，这可能不太高效。
你需要寻找的是一种贪心最佳优先搜索方法来搜索这棵树，这是可证明的最优解。也许你可以通过创建一种类似于 A* 的搜索方法来实现，但我不确定你的合理启发式方法会是什么。
我认为贪心算法并不适用。让顶点为A=0，B=1，C=2，边为AB=a-5b，BC=b+c，CA=-20。贪心算法首先选择要评估的是BC，价值为3。然后是AB，价值为-15。但是，有更好的顺序可以使用。首先评估AB，价值为-5。然后再评估BC，价值为-3。我不知道是否有更好的算法。
a[0]和a[n-1]进行操作，但对于多边形的顶点是有效的。 - laike9m