Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
1

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

01.05.2014, 16:18. Просмотров 476. Ответов 2
Метки нет (Все метки)

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2014, 16:18
Ответы с готовыми решениями:

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

Какое максимальное количество натуральных чисел можно выбрать чтобы среди них не было отличающихся в два раза
Помогите пожалуйста у меня защита курсовой завтра по С++ а задача не сделана...

Найдите индексы строки и столбца для элемента, с которого начинается самая длинная серия.
Тема задания: Массивы. Структурные типы. Классы. Задача: Определите...

Найдите индексы строки и столбца для элемента, с которого начинается самая длинная серия
Задача: Определите двумерный массив, содержащий целые числа. Будем называть...

Выбрать название продукта, для которого в 1990 г. было продано максимальное количество экземпляров продукта
Нужно сделать запрос , немогу понять в чем причина SELECT ,...

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

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




дальше не знаю, помогите плиз
0
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
16.05.2014, 12:58  [ТС] 3
Количество дней k определил. Как одно подобрать именно дни, которые надо включить?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2014, 12:58

Найдите среди элементов массива тот, у которого сумма всех делителей имеет максимальное значение
Дан одномерный массив. Найдите среди его элементов тот, у которого сумма всех...

Добрый день. Подскажите, каким образом в system можно задать условие?
Добрый день. Подскажите, возможно ли в system задать условие? Например чтобы...

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


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru