Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ поис оптимального варианта

Автор: compiler 15.12.2007 22:17

Добрый день!
Сегодня был на районной олимпиаде и встретил) такую задачу

В кондитирском магазине лежит ряд пакетов с пакетами. Для каждого пакета известно количество конфет в нем . Покупатель может взять в одну руку два соседних пакета и в другую - тоже два соседних покета(возможно, в другом конце ряда). При этом он хочет, чтобы количество конфет в четырех взятых им пакетах было максимальным. Напишите программу Sweet, которая решает за покупателя эту задачу.
4<=количество пакетов<=80
входные данные
кол. пакетов, кол. конфет в каждом пакете
выходные данные
намера пакетов(попарно)

вотс..
чесно говоря варианты есть, но хотелось бы узнать оптимальный алгоритм.

заранее благодарен.

Автор: andriano 15.12.2007 22:41

Я бы действовал так:
За первый проход нашел максимальную пару из двух подряд идущих пакетов.
Исключил найденную пару.
За второй проход нашел вторую пару среди осавшихся.
Если вторая пара будет лежать по обе стороны от первой, то перекомпоновать пары.

Сложность O(n).

Автор: compiler 15.12.2007 23:04

пожалуй да... это было бы хорошее решение...

спасибо!