Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
5 / 6 / 4
Регистрация: 17.09.2013
Сообщений: 337
1

Лесенка

15.02.2014, 21:55. Просмотров 1262. Ответов 1
Метки нет (Все метки)

Ограничение времени: 1 с
Ограничение памяти: 64 M


На каждой из N+2 ступенек лестницы записано целое число, причем на первой и последней ступеньке записано число 0. На первой ступеньке стоит человек, которому необходимо подняться на последнюю ступеньку. За один шаг он может подниматься на любое число ступенек, не превосходящее K.

Подсчитаем сумму всех чисел, написанных на ступеньках, на которые наступил человек. Найдите наибольшее возможное значение этой суммы.
Input

Первая строка стандартного потока ввода содержит количество тестовых случаев Т. Каждый тестовый случай представляет собой описание лестницы.

Описание лестницы состоит из трех строк.

В перой строке записано число N, 0 ≤ N ≤ 1000.

Во второй строке записано N целых чисел, не превосходящих по модулю 1000, разделенных пробелами - числа, записанные на ступеньках (за исключением первой и последней ступеньки, на которых записаны нули).

В третьей строке записана максимальная величина шага человека K, 1 ≤ K ≤ N.
Output

Для каждого тестового случая выведите максимально возможную сумму чисел, записанных на ступеньках, на которые наступил человек.
Подскажите хоть какой-нибудь алгоритм.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.02.2014, 21:55
Ответы с готовыми решениями:

Лесенка
На каждой из n + 2 ступенек лестницы записано целое число, причем на первой и на последней...

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

Лесенка
Привет программисты!!! Подскажите пожалуйста код программы! Задача программы: при нажатии кнопки...

Шифр «Лесенка»
К открытому тексту был применен шифр «Лесенка». Восстановите сообщение по шифрованному тексту...

1
90 / 82 / 40
Регистрация: 06.02.2014
Сообщений: 122
16.02.2014, 00:55 2
Для каждой ступеньки посчитаем максимальное число, которое человек мог набрать, если он дошел до этой ступеньки и остановился на ней.
Для понятности буду обозначать это значение https://www.cyberforum.ru/cgi-bin/latex.cgi?q_i для https://www.cyberforum.ru/cgi-bin/latex.cgi?i-той ступеньки

https://www.cyberforum.ru/cgi-bin/latex.cgi?q_0 очевидно, равно 0.
для всех остальных: найти среди предыдущих https://www.cyberforum.ru/cgi-bin/latex.cgi?K ступенек такую ступеньку, у которой https://www.cyberforum.ru/cgi-bin/latex.cgi?q_i максимально, прибавить к этому числу число, записанное на текущей ступеньке.

Таким образом получаем в конце https://www.cyberforum.ru/cgi-bin/latex.cgi?q_{N+1} - ответ.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.02.2014, 00:55

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Лесенка из пробелов и #
нужно создать программу в которой пользователь будет вводить число, а результат должен быть такой...

Шифр «Лесенка»
К открытому тексту был применен шифр «Лесенка». Восстановите сообщение по шифрованному тексту...

программа лесенка
Напишите программу вывода на экран последовательности целых чисел, отличающихся на единицу, в виде...

Лесенка из зведочек
Написать класс с методом рисующий лесенку из звездочек, высота равна ширине, и передается в метод в...


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

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

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