Блог пользователя tamir

Автор tamir, 11 лет назад, По-русски

Привет всем. Нужна ваша помощь по решению задачи (8C - Looking for Order). Спасибо за внимание.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Не все не читают теги))

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Дам маленькую подсказку. O(N2 * 2N), но на практике всё гораздо меньше.

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Можно за O(2n·n). Вообще основная стандартная идея такая. Будем делать динамику по множеству взятых объектов. Хранить множество можно в виде числа. Если представить число в двоичном виде, то можно сказать, что элементы, в разрядах которых стоят единицы, входят в множество, кодируемое данным числом.

Переход в динамике — возьмем один или два предмета. Как взять один ---понятно: переберем удаляемый элемент, посмотрим, что мы насчитали для множества, где этот элемент отсутствует и прибавим квадрат расстояния от него до сумки. Если мы хотим O(2n·n2), то с двумя можно делать примерно то же самое, перебрать их, посмотреть ответ для множества без них и прибавить расстояние, которое нужно пройти, чтобы их собрать (нужно сложить расстояние между этими предметами и расстояния от каждого предмета до сумки).

Теперь, чтобы стало O(2n·n), надо понять, что всегда нужно убирать предмет с самым маленьким номером. То есть, останется перебрать только один предмет из пары. Почему это так? Потому что порядок взятия не важен и когда-то нам в любом случае придется брать этот предмет. Если мы возьмем его сейчас, мы ничего не испортим.

Код: 2039949