Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/15: Рейтинг темы: голосов - 15, средняя оценка - 4.60
tennisru
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
1

Динамическое программирование. Лесенка

17.06.2012, 23:27. Просмотров 2745. Ответов 1
Метки нет (Все метки)

Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова.

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

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

Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы. Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Количество ступеней не превышает 1000, числа, написанные на ступенях, не превосходят по модулю 1000.

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

Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова.
ссылка
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var x1,y1,x2,y2:longint;
st,i,x,a,y:longint;
mas,p,d:array[-2..2000] of longint;
 
begin
 assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
 
 
read (x);
for i:=1 to x do
read (d[i]);
d[0]:=0;
d[-1]:=100000000;
for i:=2 to x do
if d[i-1]> d[i-2] then begin
 d[i]:=d[i-1]+d[i];p[i]:=i-1;
 end else  begin
 d[i]:=d[i-2]+d[i];p[i]:=i-2;
 end;
writeln (d[x]);
 
  while p[i]<>0 do
    begin
    inc(st);mas[st]:=p[i];i:=p[i];
    end;
 
for i:=st downto 1 do
 write (mas[i], ' ');
write (x);
end.
можете сказать почему ва 1 тест
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2012, 23:27
Ответы с готовыми решениями:

Задача на динамическое программирование
Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали...

Динамическое программирование: найти количество N-значных трипростых чисел
Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют...

Динамическое программирование
Здравствуйте , кому ни трудно помогите не с простой задачкой . Задача сделана по предмету...

Динамическое программирование
скиньте пожалуйста 2 задачи на тему Динамическое программирование

1
Dani
1398 / 642 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
17.06.2012, 23:58 2
d[0] и d[-1] должны быть -1000000, т.к. d[0], если оно равно 0, может оказаться больше, чем d[1], которое может равняться -1.

Добавлено через 15 минут
Я написал решение, оно прошло. Если нужно, то вот:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
var a, d, way: array [0..1001] of longint;
    i, n: longint;
 
 
 
procedure OutWay (n: longint);
begin
 
 if (way[n] = 0) then
  begin
   write (n,' ');
   exit;
  end;
 OutWay (way[n]);
 write (n,' ');
end;
 
 
 
begin
assign (input,'input.txt'); reset (input);
assign (output,'output.txt'); rewrite (output);
read (n);
 
for i:= 1 to n do
 read (a[i]);
 
 
d[1]:= a[1];
 
for i:= 2 to n do
 if d[i-1] > d[i-2] then
  begin
   d[i]:= d[i-1] + a[i];
   way [i]:= i-1;
  end
 
 else
  begin
   d[i]:= d[i-2] + a[i];
   way [i]:= i-2;
  end;
 
 
 
writeln (d[n]);
OutWay (n);
 
end.
1
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2012, 23:58

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

Динамическое программирование, гвоздики
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить...

Задача на динамическое программирование
Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k...

Динамическое программирование. Stack
Начал основывать динамику и начал со стэка, нужна помощь запуска программы. Вот процедуры и...

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


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

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

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