Форум программистов, компьютерный форум CyberForum.ru

Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день - C++

Восстановить пароль Регистрация
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
01.05.2014, 16:18     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день #1
Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте. Поскольку главный редактор газеты настаивает, чтобы название статьи было “Восхождение и спуск”, решено было не упоминать о некоторых днях похода, рассказав лишь о восхождении, причем если статья будет рассказывать о x1-ом, x2-ом, …, x2k + 1-ом (x1 < x2 < … < x2k + 1) днях, то должно выполняться условие hx1 < hx2 < … < hxk < hxk + 1 > hxk + 2 > … > hx2k + 1.
Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день.
Входные данные
Входные данные находятся в текстовом файле с именем report.in.
Первая строка входного файла содержит число N – количество дней в походе (1 ≤ N ≤ 100).
Следующая строка содержит N целых чисел — h1, h2, …, hN (1 ≤ hi ≤ 104).
Выходные данные
Выходные данные записываются в текстовый файл report.out.
В первой строке выходного файла выведите число k.
Затем выведите 2k + 1 число — номера дней, репортаж о которых следует включить в статью, в возрастающем порядке.
Если возможных ответов несколько, выведите любой.
Пример
report.in
7
0 3 1 10 7 2 1
report.out
2
1 2 5 6 7
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2014, 16:18     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день
Посмотрите здесь:

C++ Какое максимальное количество натуральных чисел можно выбрать чтобы среди них не было отличающихся в два раза
C++ Дано N целых чисел. Требуется выбрать из них максимальное число.
Найдите индексы строки и столбца для элемента, с которого начинается самая длинная серия C++
C++ Дается последовательность. Найдите максимальное произведение среди всех пар этих чисел
C++ Найдите индексы строки и столбца для элемента, с которого начинается самая длинная серия.
C++ Определить элемент этого массива, в двоичной записи которого максимальное число единиц
Создать двумерный массив, каждый элемент которого задается случайным образом C++
Найти максимальное число k, для которого существует точка прямой, покрытая k отрезками заданного набора C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
15.05.2014, 01:11  [ТС]     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день #2
Для каждого из N дней подсчитайте b[i] = длину наибольшей убывающей подпоследовательности высот начинающейся на i-м дне, и a[i] = длину наибольшей возрастающей подпоследовательности заканчивающейся на i-м дне. Это типичная задача на динамическое программирование, написать ее можно и без рекурсии.

Число k в ответе, соответственно, будет равно Точнее, max_{1<=i<=N} (min(a[i], b[i]) - 1), а последовательность чисел получается восстановлением и обрезанием до длины k двух соответствующих подпоследовательностей.




дальше не знаю, помогите плиз
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
16.05.2014, 12:58  [ТС]     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день #3
Количество дней k определил. Как одно подобрать именно дни, которые надо включить?
Yandex
Объявления
16.05.2014, 12:58     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день
Ответ Создать тему
Опции темы

Текущее время: 13:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru