SPOJ Problemset (Classical): 9386. Переставить II # [MAIN112]

Question

Описание проблемы (приведено здесь для удобства):

Для последовательности из N целых чисел, A1, A2, ..... AN

Мы можем вычислить коэффициент устойчивости P как

P = сумма всех (abs (Ai-Ai-1) * C [i]), где 2 <= i <= N </p>

C [i] - это стоимость помещения числа в позицию i

Ваша задача - найти минимальное P для заданных N чисел, учитывая все их сочетания.

---

Мне просто нужно подтолкнуть правильное направление относительно общего подхода к решению этой проблемы.(Небольшие кусочки псевдокода приветствуются, но я уверен, что в значительной степени закодирую решение, как только общий алгоритм станет ясен)

Я думал об этом довольно долго, но все еще застрял в достижениипри любом решении, которое удовлетворяет ограничениям этой задачи (N <= 15) Подход методом грубой силы, по-видимому, эффективен только до N = 10. </p>

---

Прежде всего, для максимально возможного тестаслучай 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)))