| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Здравствуйте.
Некоторое врем я пытаюсь решить задачу Horses ( ENG, RUS ) с IOI 2015 ( но у меня кроме первой подзадачи другие не получается решить :( ).
Я читал разбор с официального сайта ( но не очень в нем разобрался :( ).
Пожалуйста помогите решить данную задачу на 100% ( или хотя бы иначе объясните разбор ).
Огромное Вам Спасибо.
Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)
Мой метод отличается от метода в разборе.
Первым делом нужно понять, что выгодно продавать лошадей разом в один из дней.
Теперь нужно выбрать такой день i, когда X1 * X2 * ... * Xi * Yi максимально.
Главная проблема — модуль. Решаем её с помощью логарифмов — по их свойству log(A * B) = log(A) + log(B). Заметим, что log очень медленно растущая функция.
Можно построить дерево отрезков, в i-ом листе будет храниться log(X1) + log(X2) + ... + log(Xi) + log(Yi), теперь просто в каждой вершине будем хранить пару (максимум - на - отрезке, индекс). При updateX нужно будет делать обновление на отрезке — отнимаем log(Xi) от всех j > = i, потом прибавляем log(newXi) ко всем j > = i. При updateY просто единичное обновление.
Теперь мы умеем определять день, в который нам выгодно продать лошадей. Остальное — детали реализации. ;)
Спасибо.
Я пытался решить данную задачу так.
Пусть dp[i] — это максимальная прибыль которую можно получить, если в начале i-ого года у нас будет 1 лошадь.
Тогда dp[n-1] = X[n-1] * Y[n-1];
А для всех остальных i от n-2 до 0
А ответ это dp[0];
Верно, что это решение выдаёт TL, но у меня кроме Tl также WA.
Подскажите почему? ( Из за модуля ? )
Спасибо.
Потому что dp[i+1] может быть меньше по модулю, но больше по значению. Так как y[i] влезает в тип, то можно отдельно хранить флаг, что dp[i+1] переполнилось (т.е. заведомо больше любого числа, в т.ч. y[i]).
Which part of the analysis don't you understand?
Observation 2 and 3.