SPOJ 问题集（古典）：9386。重新编曲 II #[MAIN112]

Question

问题描述（为方便起见，在此处引用）：

对于 N 个整数的序列，A1, A2, ..... AN

我们可以计算稳定因子P，为

P = 所有 (abs(Ai-Ai-1)*C[i]) 之和，其中 2 <= i <= N

C[i] 是将数字放在位置 i 的成本

您的任务是找到给定 N 个数字的最小 P，考虑到 它们的所有不同排列。

---

我只需要在正确的方向上推动，关于解决这个问题的一般方法。 （欢迎使用少量伪代码，但一旦总体算法大致清晰，我就有信心编写出一个解决方案）

我已经考虑了很长一段时间，但仍然坚持找到满足以下条件的解决方案：该问题的约束条件 (N <= 15) 暴力方法似乎只有在 N=10 时才表现良好。

---

首先，对于最大可能的测试用例 N=15，我不相信你能够枚举并考虑所有 15 个！排列以便在足够好的时间内找到答案，因为复杂性类别不允许这样做。

因此我们需要做出几个简化的假设来减少这个搜索空间。这就是我被困住的地方。或者也许这只是一种更聪明的方式来开始遍历这个排列空间？

我尝试使用动态编程来解决这个问题，因为排列共享许多公共位，可以在必要时预先计算（记忆）并存储和重用，例如。 A[] = 123456 & A[] = 123465 两者都会给出 1234- 相同的部分和，但这没有成功，因为你仍然需要经历 15！排列，并且在此之前会 TLE，所以它不好。

另一个想法是处理连续 A 和 C[] 的所有元素之间差异的所有可能排列，并首先找到将产生最小 abs(A[i]-A[j])*C[k ] 从所有这些中取出值，分配这些 &将它们标记为已使用，然后继续使用 i 或 j 中的一个来形成下一对，再次迭代并重复。这应该在多项式时间内完成（我猜测大约是 n^3），但对于某些示例，该假设失败。

我认为这个问题不应该那么困难，需要将其转换为某种图形问题 - 其中 A[i]、A[j] 形成节点，而 C[k] 是连接这些节点的边的成本，或者也许是一些布尔 SAT 问题……这一切似乎完全走上了错误的轨道。

如果您用 google 搜索此问题，除了托管此问题的 SPOJ 站点之外，您可能几乎找不到任何与此问题相关的内容。

非常感谢。

Answer 1

您可以对子集使用 O(n*2^n) 空间、O(n^2*n^2) 时间动态规划算法来求解。

关键的见解是，当您从左到右构建最佳解决方案时，只有先前放置的数字和使用的子集很重要，而不是事物在使用的子集中放置的顺序。

与旅行推销员问题的解决方案具有基本相同的结构。

该计算 与您的 DP 想法走上正轨。我们的见解是，所有这些部分路径之后的最佳路径是相同的

1235

1325

2135

2315

3125

3215

因此，您实际上不需要探索所有可能的排列，只需探索那些具有最佳部分路径的排列即可。

下面是一些实现所描述算法的 TLE Python 代码，但由于 Python 中的常数因子减慢而失败。我转换为 C++ 并获得了 AC。

global A
global C

A = []
C = []

def Solve(used, last, cache):
  if (used, last) in cache:
      return cache[(used, last)]
  cur_pos = len(used)
  if cur_pos == len(A):
    return 0

  mn = 1e10
  for idx in range(len(A)):
      if not idx in used:
          next_used = used.union([idx])
          subcost = Solve(next_used, A[idx], cache)
          additional = C[cur_pos] * abs(last - A[idx])
          mn = min(mn, subcost + additional)
  cache[(used, last)] = mn
  return mn

T = int(raw_input())
for i in range(T):
  N = int(raw_input())
  A = map(int, raw_input().split())
  C = map(int, raw_input().split())
  cache = {}
  print min(Solve(frozenset([idx]), A[idx], cache) for idx in range(len(A)))