以最优的方式减少序列

Question

给出了一个序列a的n数。序列a的约简被定义为用max(a[i],a[i+1])替换元素a[i]和a[i+1]。

每个缩减操作都有一个定义为max(a[i],a[i+1])的成本。在n-1缩减后，得到了一个长度1序列。

现在，我们的目标是打印给定序列a的最优缩减的代价，以便得到长度为1的序列具有最小的成本。

例如：

1

2

3

Output :

5

O(N^2)解是平凡的。有什么想法吗？

EDIT1:人们都在问我的想法，所以我的想法是成对地遍历序列，对每对检查成本，最后用最少的成本减少对。

1 2 3
 2 3     <=== Cost is 2

因此，将上述顺序降为

2 3

现在再次遍历序列，我们得到的成本为3。

2 3
 3       <=== Cost is 3

所以总成本是2+3=5

该算法为O(N^2)。这就是为什么我要求一些更优化的想法。

Answer 1

O(n) 解决方案：

高级级别：

其基本思想是反复将任何小于其邻居e和nl的元素与最小的邻居ns合并。这会产生最小的成本，因为合并的成本和结果都是max(a[i],a[i+1])，这意味着任何合并都不能使元素比当前更小，因此e最便宜的可能合并是与ns合并，而且合并不会增加任何其他可能的合并的成本。

这可以通过一次传递算法来完成，方法是将元素堆栈按递减顺序从我们的数组中保持。我们将当前元素与其两个邻居(其中一个是堆栈的顶部)进行比较，并执行适当的合并直到完成。

Pseudo-code:

stack = empty
for pos = 0 to length
  // stack.top > arr[pos] is implicitly true because of the previous iteration of the loop
  if stack.top > arr[pos] > arr[pos+1]
    stack.push(arr[pos])
  else if stack.top > arr[pos+1] > arr[pos]
    merge(arr[pos], arr[pos+1])
  else while arr[pos+1] > stack.top > arr[pos]
    merge(arr[pos], stack.pop)

Java代码：

Stack<Integer> stack = new Stack<Integer>();
int cost = 0;
int arr[] = {10,1,2,3,4,5};
for (int pos = 0; pos < arr.length; pos++)
  if (pos < arr.length-1 && (stack.empty() || stack.peek() >= arr[pos+1]))
    if (arr[pos] > arr[pos+1])
      stack.push(arr[pos]);
    else
      cost += arr[pos+1]; // merge pos and pos+1
  else
  {
    int last = Integer.MAX_VALUE; // required otherwise a merge may be missed
    while (!stack.empty() && (pos == arr.length-1 || stack.peek() < arr[pos+1]))
    {
      last = stack.peek();
      cost += stack.pop(); // merge stack.pop() and pos or the last popped item
    }
    if (last != Integer.MAX_VALUE)
    {
      int costTemp = Integer.MAX_VALUE;
      if (!stack.empty())
        costTemp = stack.peek();
      if (pos != arr.length-1)
        costTemp = Math.min(arr[pos+1], costTemp);
      cost += costTemp;
    }
  }
System.out.println(cost);

Answer 2

我感到困惑的是，您是指降低“计算成本”的“成本”，即需要时间max(a[i],a[i+1])的操作，还是您想要计算的简单操作。如果是后者，则下列算法优于O(n^2)：

1. 对列表进行排序，或者更精确地定义b[i] s.t。a[b[i]]是排序列表: O(n)，如果可以使用基排序，则使用O(n log )。
2. 从排序列表中的第二最低项i开始:如果左/右低于i，则对每个项执行约简: O(1)，总共从2更新列表O(n)。

我不知道这是否是最优解，但对于整数是O( n)，否则是O(n log N)。

编辑:意识到删除预计算步骤使其更简单。

Answer 3

贪婪的方法确实有效。

你总是可以减少最小的数目与其较小的邻居。

证明：我们必须在某个点上减少最小数。邻居的任何减少都会使邻居的值至少相同(可能)大，因此减少最小元素ai的操作总是要花费c>=min(ai-1，ai+1)。

现在我们需要

1. 快速查找/移除最小数目
2. 找到它的邻居

我要用两个RMQ。以二进制搜索的形式执行操作2。给出了O(N * log^2(N))

编辑：第一次RMQ -值。当您移除元素时，请在其中放置一些大值。

第二个RMQ -“存在”。0或1(值存在/不存在)。例如，要找到ai的左邻居，您需要找到最大的l，即sum[l,i-1] = 1。