Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование: последовательности
---> 1 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: 1 Отображать по:
#1384
Репортаж
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Для N дней заданы высоты. Требуется выделить максимальное подмножество дней нечетной длины (2K+1), так что бы впервые K дней высота увеличивалась,на K+1 день был достигнут максимум, а в оставшиеся дни высота уменьшалась.

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте hi. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x1-ом, x2-ом, …, x2k+1-ом (x1 < x2 < … < x2k+1)) дне, то должно выполняться условие hx1 < hx2 < … < hxk < hxk+1 > hxk+2 > … > hx2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.

Входные данные

Первая строка входного файла содержит число N – количество дней в походе (1 ≤ N ≤ 100). Следующая строка содержит N целых чисел – h1, h2, …, hN (0 ≤ hi ≤ 104).

Выходные данные

В первой строке выходного файла выведите число k. Затем выведите 2k+1 число - номера дней, репортаж о которых следует включить в статью, в возрастающем порядке. Если возможных ответов несколько, выведите любой.

Примеры
Входные данные
7
0 3 1 10 7 2 1
Выходные данные
2
1 2 5 6 7
Входные данные
4
1 2 3 4
Выходные данные
0
1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест