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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
#1

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

01.05.2014, 16:18. Просмотров 342. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день (C++):

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

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

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

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

Выбрать название продукта, для которого в 1990 г. было продано максимальное количество экземпляров продукта - SQL Server
Нужно сделать запрос , немогу понять в чем причина SELECT , MAX(ITEM.quantity) FROM PRODUCT INNER JOIN ITEM ON...

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

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 можно задать условие? - CMD/BAT
Добрый день. Подскажите, возможно ли в system задать условие? Например чтобы если a=1 записывал одно, а если a=2 записывал другое. Заранее...

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

Найти максимальное число, запись которого можно получить вычеркиванием цифр как из двух последовательностей - C#
Пусть x и y - две бинарных последовательности (т.е. элементы последовательностей - нули и единицы); x и y можно рассматривать как запись в...

Каким образом можно во внешнем запросе выбрать все переменные, которые находятся внутри функции? - Oracle
Добрый день. У меня есть пакет с функцией внутри которой производятся различные действия со многими переменными. Каким образом...


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

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

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