#c #algorithm #dynamic-programming
#c #алгоритм #динамическое программирование
Вопрос:
У меня вопрос о динамическом программировании от USACO. (изучение информатики).
Текст вопроса находится здесь: http://pastebin.com/MiJ5aEWc
Я подумал, что это может быть аналогично подпоследовательности Max Inc, но может ли кто-нибудь указать мне правильное направление?
Спасибо!
Комментарии:
1. Это из недавнего экзамена?
2. Нет, я действительно вчера выиграл бронзовый приз, думал. Это было действительно просто! 😀
Ответ №1:
ДА. Это можно решить в O (n log n), динамическое программирование:
сначала отсортируйте коров по координате x и сопоставьте типы пород с целыми числами [1 ..k]. (k <= n) : O (n log n)
определите dp [i] = максимальный индекс j, такой, что от j-й коровы до i-й отображаются все породы или -1, если не существует.
поскольку для каждого k <= dp[i] допустим диапазон коров [k, i] и i < j -> dp[i] <= dp[j], вы можете решить часть dp в O (n), записав количество коров каждого типа в диапазоне коров [dp[i], i].
Комментарии:
1. Меня смущает обозначение вокруг диапазона dp [i] [d, i]. Можете ли вы объяснить, что это значит? (может быть, подробнее остановиться на этой части?)
2. Отредактировано; допустимый диапазон [a, b] означает, что диапазон коров содержит все типы пород.
3. Извините, если я вас беспокою, вы можете прекратить комментировать, если хотите, но поскольку dp[i] равен максимальной j-й cow, как «i < j» в операторе «i < j -> dp[i] <= dp[j] «. Я определенно понимаю часть k <= dp[i], но есть какой-нибудь псевдокод «для цикла» (терминология профессора)? Огромное спасибо!
4. те i, j, которые находятся в другой области видимости, вы можете заменить их на x и y: x < y -> dp[x] <= dp[y]