Помогите пожалуйста решить задачу Horses с IOI 2015.

Блог пользователя Barsic

Автор Barsic, история, 8 лет назад, По-русски

Здравствуйте.

Некоторое врем я пытаюсь решить задачу Horses ( ENG, RUS ) с IOI 2015 ( но у меня кроме первой подзадачи другие не получается решить :( ).

Я читал разбор с официального сайта ( но не очень в нем разобрался :( ).

Пожалуйста помогите решить данную задачу на 100% ( или хотя бы иначе объясните разбор ).

Огромное Вам Спасибо.

ioi 2015, задачи и решения

Barsic
8 лет назад
6

Комментарии (6)

Написать комментарий?

Barsic

8 лет назад, # |

Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)

→ Ответить

Azret

8 лет назад, # |

← Rev. 7 →

Мой метод отличается от метода в разборе.

Первым делом нужно понять, что выгодно продавать лошадей разом в один из дней.

Теперь нужно выбрать такой день i, когда X₁ * X₂ * ... * X_i * Y_i максимально.

Главная проблема — модуль. Решаем её с помощью логарифмов — по их свойству log(A * B) = log(A) + log(B). Заметим, что log очень медленно растущая функция.

Можно построить дерево отрезков, в i-ом листе будет храниться log(X₁) + log(X₂) + ... + log(X_i) + log(Y_i), теперь просто в каждой вершине будем хранить пару (максимум - на - отрезке, индекс). При updateX нужно будет делать обновление на отрезке — отнимаем log(X_i) от всех j > = i, потом прибавляем log(newX_i) ко всем j > = i. При updateY просто единичное обновление.

Теперь мы умеем определять день, в который нам выгодно продать лошадей. Остальное — детали реализации. ;)

→ Ответить

Barsic

8 лет назад, # ^ |

Спасибо.

Я пытался решить данную задачу так.

Пусть dp[i] — это максимальная прибыль которую можно получить, если в начале i-ого года у нас будет 1 лошадь.

Тогда dp[n-1] = X[n-1] * Y[n-1];

А для всех остальных i от n-2 до 0

dp[i] = (max(Y[i], dp[i+1]) * X[i]) % ( 10^9 + 7 );

А ответ это dp[0];

Верно, что это решение выдаёт TL, но у меня кроме Tl также WA.

Подскажите почему? ( Из за модуля ? )

Спасибо.

→ Ответить

Ralsei

8 лет назад, # ^ |

Потому что dp[i+1] может быть меньше по модулю, но больше по значению. Так как y[i] влезает в тип, то можно отдельно хранить флаг, что dp[i+1] переполнилось (т.е. заведомо больше любого числа, в т.ч. y[i]).

→ Ответить