Снова нужны идеи решения задачи на жадный алгоритм

Revision ru3, by dmkz, 2018-07-14 23:56:17

Здравствуйте! Пытаюсь сдать задачу "882. Губернатор" с сайта acmp.ru. Недавно я создавал аналогичный пост для другой задачи, под которым подсказали, что в задачах такого рода должен работать жадный алгоритм и нужно лишь определить предикат для сортировки.

В этой же задаче я понял, что ответ не зависит от K и необходимо минимизировать сумму:

an·an - 1·...·a2·b1 + an·an - 1·...·a3·b2 + an·an - 1·...·a4·b3 + ... + an·bn - 1 + bn

Здесь индексами обозначена последовательность взятия.

Я генерировал маленькие случайные тесты, для которых можно перебрать все n! перестановок и пробовал подобрать предикат, но все безрезультатно. Максимально близко к случайным тестам размера 10 подошел предикат , где — произведение всех ai. На этом идеи кончились и нужна помощь. Может из-за маленького n решение предполагает динамику за O(n2) времени с памятью O(n), но с ней тоже не вяжется.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian dmkz 2018-07-14 23:56:17 506
ru2 Russian dmkz 2018-07-14 23:46:35 510
ru1 Russian dmkz 2018-07-14 23:39:17 1198 Первая редакция (опубликовано)