Вопрос о динамическом программировании

Цирк разрабатывает представление на вышке, состоящее из людей, стоящих друг над другом. плечи. По практическим и эстетическим причинам каждый человек должен быть и ниже, и легче человека ниже его или ее. Учитывая рост и вес каждого человека в цирке, напишите метод для вычисления как можно большего количества людей. в такой башне.

ПРИМЕР:
Ввод (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Результат: Самая длинная башня имеет длину 6 и включает сверху вниз: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

Кто-то предложил мне следующее: Это можно сделать следующим образом:

  1. Отсортируйте входные данные в порядке убывания веса и найдите самую длинную убывающую последовательность высоты.
  2. Отсортируйте входные данные в порядке убывания высоты и найдите самую длинную убывающую последовательность веса.

Возьмите максимум 1 и 2.

Я не понимаю, почему нам нужно выполнить оба шага 1 и 2. Мы просто не можем сделай 1 и найди ответ. ЕСЛИ нет, приведите пример, в котором выполнение только шага 1 не дает ответа?

9
задан angry person 31 July 2011 в 12:36
поделиться