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

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

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

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

01.05.2014, 16:18. Просмотров 331. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2014, 16:18     Найдите максимальное k, для которого можно соответствующим образом выбрать 2k + 1 день
Посмотрите здесь:

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

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

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

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

Найти максимальное число k, для которого существует точка прямой, покрытая k отрезками заданного набора - C++
Дано n отрезков: , i=1,…,n. Найти максимальное число k, для которого существует точка прямой, покрытая k отрезками заданного набора. Число...

Создать двумерный массив, каждый элемент которого задается случайным образом - C++
Если вкратце, нужно создать двумерный массив, каждый элемент которого задается случайным образом. Вот моя программа: #include...

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

Дается последовательность. Найдите максимальное произведение среди всех пар этих чисел - C++
Е. Дается последовательность из N чисел. Найдите максимальное произведение среди всех пар этих чисел. Первая строка входного файла...

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

В целочисленном массиве найти элемент, произведение которого с предыдущим максимальное среди всех - C++
как бы сам код есть но нужно сделать что бы мы вводили кол-во символов в массиве и сами элементы были случайны #include &lt;iostream&gt; ...

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

Дано N целых чисел. Требуется выбрать из них максимальное число. - C++
народ всем привет помогите плс мои задания : 1.Дано N целых чисел. Требуется выбрать из них максимальное число. Ввод Вводится...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 определил. Как одно подобрать именно дни, которые надо включить?
Ответ Создать тему
Опции темы

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