Как нужно решать задачу?
Линия монорельса, построенная в столице Байтландии, не пользуется особой популярностью среди пассажиров. Изучив ситуацию, специалисты по транспортным потокам пришли к выводу, что место для постройки было выбрано очень неудачно. Равно как и конфигурация линии. Дело в том, что для популярности у жителей столицы новая линия должна быть кольцевой. А ещё лучше — если это были бы две кольцевые линии в разных районах города.
В итоге было решено разобрать монорельсовую дорогу и из прямолинейных участков построить две примерно одинаковые кольцевые линии. Каждая линия представляет собой многоугольник, собранный из прямолинейных участков существующей линии. При этом многоугольник должен иметь ненулевую площадь, каждый участок существующей линии должен быть использован в новых сооружениях ровно один раз, участки должны быть использованы целиком «как есть» (то есть разрезание прямолинейного участка не допускается).
Мэрия хочет, чтобы длины каждой кольцевой линии (то есть периметры многоугольников) отличались как можно меньше. Ваша задача — найти эту минимальную разницу или определить, что строительство двух кольцевых линий из существующего набора прямолинейных участков невозможно.
Формат ввода
Первая строка входных данных содержит одно целое число N (6 ≤ N ≤ 40). Вторая строка содержит N целых чисел l1, l2, …, lN (1 ≤ lN ≤ 100) — длины прямолинейных участков.
Формат вывода
Выведите одно целое неотрицательное число — наименьшую возможную разность периметров. Если построить две кольцевые монорельсовые линии нельзя, выведите -1.
Примеры:
Ввод:
6
4 4 5 4 4 4
Вывод:
1
Ввод:
7
3 2 1 1 2 3 2
Вывод:
0
Ввод:
6
1 1 1 1 1 10
Вывод:
-1
Так. Я тут подумал. И у меня возникла идея решения. Смотрите. Мы сортируем массив и делим его на две части. Берем первую половину от N и как-то проверяем можно ли составить из этих длин многоугольник, если нет выводим -1, если да, то аналогично проверяем вторую половину. А потом просто выводим их разницу. Оцените насколько правильна идея и как проверить может ли многоугольник сущестововать?
Ответы (1 шт):
Это задача о наборе суммы (subset sum), может решаться динамическим программированием - нужно набрать сумму, близкую к общей длине пополам
S <= Sum(L[i]) / 2
Осложняется условием составления многоугольника - а его можно составить, если самая длинная часть по меньшей мере на 1 меньше суммы остальных сторон - это придётся учитывать при заполнении таблицы ДП - если в сумме участвует длина P, то сумма должна быть не меньше 2P+1.