Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
slavabel
0 / 0 / 0
Регистрация: 28.03.2012
Сообщений: 2
1

Лесенка

07.12.2013, 23:52. Просмотров 1948. Ответов 1
Метки нет (Все метки)

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

Подсчитаем сумму всех чисел, написанных на ступеньках, на которые наступил человек. Найдите наибольшее возможное значение этой суммы.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var
A:array[-1000..1001] of longint;
j,n,i,k,t:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;  end;
begin
readln(N);  inc(n);
for i:=2 to n do
read(a[i]);
readln(K);
for i:=1 to n do    begin
t:=a[i-1];
 for j:=i-1 downto i-k do
 t:=max(t,a[j]);
a[i]:=a[i]+t; end;
writeln(a[n]);
end.
Пример входных данных
3
1 -1 1
2
Пример выходных данных
2
Проходит всего лишь 30%
Может кто нибудь поделиться другим решением или укажет на ошибку?

Добавлено через 5 минут
Входные данные

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

Выходные данные

Выведите максимально возможную сумму чисел, записанных на ступеньках, на которые наступил человек.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2013, 23:52
Ответы с готовыми решениями:

Динамическое программирование. Лесенка
Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа....

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

Лесенка
Ограничение времени: 1 с Ограничение памяти: 64 M На каждой из N+2 ступенек лестницы записано...

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

1
valeriikozlov
Эксперт С++
4699 / 2524 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2013, 06:08 2
Цитата Сообщение от slavabel Посмотреть сообщение
Проходит всего лишь 30%
Может кто нибудь поделиться другим решением или укажет на ошибку?
Ошибка есть. Посмотрите внимательно: Вы выводите всегда значение ступеньки не самой последней (у которой значение изначально равно 0), а предпоследней. Внимательно перечитайте условие: ступенек n+2.
Вам нужно или таким способом:
- A[] сделать размером -1000..1002
- цикл
Цитата Сообщение от slavabel Посмотреть сообщение
for i:=1 to n do begin
до n+1
- выводить значение a[n+1]
или так:
- по окончании цикла искать максимум от a[n-k+1] до a[n] и выводить его значение.
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2013, 06:08

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

Лесенка из кубиков
спасибо пошло. а вторую поможешь? Добавлено через 18 минут строит из кубиков лестницу. первая...

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

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

Лесенка из цифр.
Не могу понять, что хочет преподаватель.Задание: Постройте лесенку вверх из цифр, отстоящих на три...


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

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

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