5

Given a polygon with N vertexes and N edges. There is an int number(could be negative) on every vertex and an operation in set (*,+) on every edge. Every time, we remove an edge E from the polygon, merge the two vertexes linked by the edge (V1,V2) to a new vertex with value: V1 op(E) V2. The last case would be two vertexes with two edges, the result is the bigger one.

Return the max result value can be gotten from a given polygon.

For the last case we might not need two merge as the other number could be negative, so in that case we would just return the larger number.

How I am approaching the problem:

 p[i,j] denotes the maximum value we can obtain by merging nodes from labelled i to j.
 p[i,i] = v[i] -- base case
 p[i,j] = p[i,k] operator in between p[k+1,j] , for k between i to j-1.
and then p[0,n] will be my answer.
Second point , i will have to start from all the vertices and do the same as above as this will be cyclic n vertices n edges.
The time complexity for this is n^3 *n i.e n^4 .

Can i do better then this ?

4

2 回答 2

5

正如您正确识别（标记）的那样，这确实与矩阵乘法问题非常相似（我以什么顺序将矩阵相乘以便快速完成）。

这可以使用动态算法以多项式方式求解。

我将改为解决一个类似的、更经典（和相同）的问题，给定一个带有数字、加法和乘法的公式，用什么括号括起来它会给出最大值，例如 6+1 * 2变成(6+1)*2大于6+(1*2).

让我们表示我们的输入a1 to an实数和 o(1),...o(n-1)*或+。我们的方法将如下工作，我们将观察表示 a1,...aj 的最大公式（在括号化之后）的子问题 F(i,j)。我们将创建一个此类子问题的表，并观察 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

这经历了所有可能的选择。正确性的证明是通过对大小 n=ji 的归纳来完成的，而且非常简单。

让我们通过运行时分析：

如果我们不为较小的子问题动态保存值，则运行速度会很慢，但是我们可以使该算法在O(n^3)

我们创建了一个 *n 表 T，其中索引 i,j 处的单元格包含 F(i,j) 填充 F(i,i) 和 F(i,j) 对于 j 小于 i 在 O(1) 中完成每个单元格，因为我们可以直接计算这些值，所以我们沿对角线填充 F(i+1,i+1) （我们可以快速完成，因为我们已经知道递归公式中的所有先前值），我们重复这个 n n 对角线的时间（实际上是表中的所有对角线）并填充每个单元格需要 (O(n))，因为每个单元格有 O(n) 个单元格，我们在 O(n^2) 中填充每个对角线，这意味着我们填充了所有O(n^3) 中的表。填写表格后，我们显然知道 F(1,n) 是您问题的解决方案。

我们填表的顺序

现在回到你的问题

如果您将多边形转换为n不同的公式（一个用于从每个顶点开始）并在其上运行公式值的算法，您将得到您想要的值。

于 2013-01-19T07:45:34.793 回答
0

我认为您可以减少对蛮力搜索的需求。例如：如果有一个链

x + y + z

您可以将其替换为值为总和的单个顶点，没有比这更好的了。在处理 +ve 整数时，需要在加法之后进行乘法运算。因此，如果一切都是积极的，那么只需减少所有 + 链，然后再重复。

这样就剩下了有 -ve 数字的情况。在我看来，单个 -ve 数字的策略非常明显，对于两个 -ve 数字有一些情况（记住 - x - 是正数），对于超过 2 个 -ve 数字，它似乎变得棘手：- )

于 2013-01-19T07:50:25.897 回答