пожалуйста помогите мне решить задачу.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
пожалуйста помогите мне решить задачу.
Название |
---|
Хоть бы "пожалуйста" сказал
Эта ДП, строится так.
Большоe Спасибо
В этой задаче работает жадность. Давайте отсортим пары (Te, Ts). Теперь покажем, что можно брать элементы в порядке этой сортировки, если Tsi > Tej, где j — последний взятый элемент, а i — текущий просматриваемый. Изначально возьмем первую пару, понятно что так как она заканчивается раньше всех, то не имеет смысла брать никакую другую пару. Теперь уберем все пары, что начинаются раньше, чем заканчивается первая и получим задачу меньше исходной, для которой можно сделать аналогичные рассуждения.
Автокомментарий: текст был обновлен пользователем feruz.atamuradov (предыдущая версия, новая версия, сравнить).