[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
А кто-нибудь знает как эту задачу решать?
Vladimir Minyaylov

Topics: 9
Messages: 30

My Profile
Полный разбор писать не стоит. Ограничемся идеями:
1. Пусть есть набор бутылок от i до j. Как бы мы их не смешивали в итоге получим одно и тоже.
2. Решение основывается на ДП. F[i,j] - минимальная стоимость смешивания бутылок от i до j. Для просчета выбираешь разбиение на два множества(i...u и u+1..j). Считаешь Fij в каждом из них и добавляешь стоимость их сливания. Из всех разбиений выбираешь минимальное.
3. Если изначально получишь все суммы, то сложность выходит O(N^3). Это укладыавется в time limit.
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
Спасибо.
А я оказывается не так условие понял Вернее не дочитал
Я думал на тест:
3
40 20 60

ответ 2400
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,078