Mrrl: Мне кажется можно немного модифицировать вашу последовательность решения. Массив M сделать трехмерным M[0...n][0...S/3][0...S/3] и каждый уровень будет определять, какие суммы достижимы для множества из i элементов (т.е. первый индекс указывает число доступных элементов A[0...i]). А в конце, если разбиение существует (т.е. M[n][S/3][S/3] = 1), мы встаем на данный элемент и в обратном порядке восстанавливаем каждое разбиение.
Допустим есть массив A[1...7]. Какие требования к выводу? Можно же вывести просто элементы A[1], A[2], A[3], A[4] или отсортировать и вывести 4 первых элемента A'[1], A'[2], A'[3], A'[4]? Или это все нужно упаковать в новый массив?
@throughtheether не кажется ли вам, что построение подобного массива займет время O(n^2)? Тем более что точка со значением координаты от 11 до 17, может лежать и на большем количестве отрезков (например даны отрезки [11, 17], [11, 21], [11, 18] и т.д.).
Спасибо за ответ. То есть для каждой точки нужно будет пройтись по данному массиву? То есть в вашем примере, пока координата входной точки больше координаты отрезков, мы идем по массиву и суммируем поля?
Написано
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
