Как проблема FlowerGarden на TopCoder связана с проблемой DP -?

Я читаю этот отличный учебник Думитру по проблемам, основанным на DP здесь . И я пытаюсь придумать основанный на DP подход к проблеме FlowerGarden , упомянутой в списке задач 1D DP.

Я могу думать только о решении без -DP, которое включало бы первоначальную сортировку цветов по порядку, а затем их переупорядочивание на основе различных проверок условий, упомянутых в задаче. Это не классифицируется как DP, не так ли?

В редакционной статье также ничего не упоминается о DP. Может ли кто-нибудь случайно указать мне правильное решение этой проблемы на основе DP -?

Спасибо!

Изменить:

Я не знал, что ссылка требует регистрации. Вот в чем проблема:

Problem Statement You are planting a flower garden with bulbs to give you joyous flowers throughout the year. However, you wish to plant the flowers such that they do not block other flowers while they are visible.

You will be given a int[] height, a int[] bloom, and a int[] wilt. Each type of flower is represented by the element at the same index of height, bloom, and wilt. height represents how high each type of flower grows, bloom represents the morning that each type of flower springs from the ground, and wilt represents the evening that each type of flower shrivels up and dies. Each element in bloom and wilt will be a number between 1 and 365 inclusive, and wilt[i] will always be greater than bloom[i]. You must plant all of the flowers of the same type in a single row for appearance, and you also want to have the tallest flowers as far forward as possible. However, if a flower type is taller than another type, and both types can be out of the ground at the same time, the shorter flower must be planted in front of the taller flower to prevent blocking. A flower blooms in the morning, and wilts in the evening, so even if one flower is blooming on the same day another flower is wilting, one can block the other.

You should return a int[] which contains the elements of height in the order you should plant your flowers to acheive the above goals. The front of the garden is represented by the first element in your return value, and is where you view the garden from. The elements of height will all be unique, so there will always be a well-defined ordering.

Редактировать два:

Пример 1:

высота={5,4,3,2,1}

цветение={1,1,1,1,1}

увядать={365,365,365,365,365}

Возвращает :{1, 2, 3, 4, 5}

Все эти цветы распускаются 1 января и увядают 31 декабря. Поскольку все они могут блокировать друг друга, вы должны упорядочить их от самых низких до самых высоких.

Пример 2:

ч={5,4,3,2,1}

б={1,5,10,15,20}

ш={4,9,14,19,24}

Возвращает :{5, 4, 3, 2, 1} Один и тот же набор цветов теперь цветет в разное время. Так как они никогда не будут блокировать друг друга,вы можете расположить их от самого высокого к самому низкому, чтобы самые высокие оказались как можно дальше вперед.

Пример 3 :высота={5,4,3,2,1}

цветение={1,5,10,15,20}

увядать={5,10,14,20,25}

Возвращает :{3, 4, 5, 1, 2} Разница здесь в том, что третий тип цветка увядает на день раньше, чем распускается четвертый цветок. Следовательно, мы можем поставить сначала цветы высоты 3, затем цветы высоты 4, затем высоты 5 и, наконец, цветы высоты 1 и 2. Заметим, что мы могли бы также сначала расположить их высотой 1, но это не так. в результате максимально возможная высота будет первой в саду.