ДM
одна из веток может складываться до MAX_INT
Size: a a a
Rust/Verona LGBTTQQIAAPС++ Iran political tutorial dick measurement strikeforce
255 membersпожаловаться на группу
2021 February 04
A
нахуя там мемоизация? чтобы сэкономить на нескольких вызовах?
чтобы алгоритм из O(2^V) переделать в O(V^2), где V — это множество состояний после применения операций
A
в целом, да, сэкономить на нескольких вызовах
ДM
Переслано от Да Melon
что мне делать с той веткой в которой операция +1?
ДM
Переслано от Да Melon
одна из веток может складываться до MAX_INT
A
ты сейчас реализовываешь top-down dp. Почитай про bottom-up
A
Или я могу решение тупо скинуть))
ДM
Artem
ты сейчас реализовываешь top-down dp. Почитай про bottom-up
что это
P
Artem
в целом, да, сэкономить на нескольких вызовах
вот только на самом деле там K*2^V, а ты будешь переделывать его в M*V^2, где M>>K.
P
потому надо осторожнее с этим
A
что такое M / K тут?)
P
к — стоимость тривиальной реализации, м — стоимость реализации с мемоизацией. Константы
P
(да, на самом деле там не просто М, а чуть сложнее, но аппроксимируем это как среднее)
A
Это константы, так что хуй забей
P
Artem
Это константы, так что хуй забей
пахнет наивностью. Эти константы на порядки могут отличаться
A
пахнет наивностью. Эти константы на порядки могут отличаться
Докажи, что отличаются раз клеймишь. И для O большого — похуй. Я хуй знает зачем ты сюда со своими константаим пришел))
P
для К можно всё на месте посчитать не выходя из регистров, для М ты будешь ебать память
P
ебать память дороже чем считать
P
вот такие потом становятся ДБА и пишут квери, которые вместо 500мс выполняются 3 минуты