Платная лестница

@newyork7776 · Регистрация: 21.05.2013

Студворк — интернет-сервис помощи студентам

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
В первой строке входного файла вводится одно натуральное число N100 — количество ступенек.
В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

пример
3
1 2 3
ответ 4

@salam · 10.11.2013, 15:26

я ничего не понимаю. только что 100 баллов получил за это.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{
    int n;
    cin >> n;
    vector<int> ans(n), cost(n);
    for(int i=0; i < n; ++i)
        cin >> cost[i];
    ans[0] = cost[0];
    ans[1] = cost[1];
    for(int i=2; i < n; ++i)
        ans[i] = minimalne(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}

@newyork7776 · 10.11.2013, 15:27 **[ТС]**

я тоже не понимаю как?

@salam · 10.11.2013, 15:28

попробуйте сдать код из моего последнего комментария. ) мне интересно, что будет.

@newyork7776 · 10.11.2013, 15:30 **[ТС]**

пашет 100 балов

Добавлено через 7 секунд
а мой почему нет?

@salam · 10.11.2013, 15:33

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

@D7ILeucoH · 15.10.2017, 10:58

Во-первых, ответ не 4, а 2...

@DobroAlex · 15.10.2017, 11:09

D7ILeucoH, во-первых, это некропостинг

@D7ILeucoH · 15.10.2017, 12:02

Модер, зачем ты удалил моё сообщение!? В этой теме нет правильного ответа!
Сам попробуй! Ввод:
5
1 2 3 4 5
Вывод: 9
А надо: 6!

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

@newyork7776 351 / 344 / 279 Регистрация: 21.05.2013 Сообщений: 1,312

	Платная лестница 10.11.2013, 00:30. Показов 33091. Ответов 27 Метки нет (Все метки) Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. В первой строке входного файла вводится одно натуральное число N100 — количество ступенек. В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх). Выведите одно число — наименьшую возможную стоимость прохода по лесенке. пример 3 1 2 3 ответ 4 Миниатюры 0

@newyork7776 351 / 344 / 279 Регистрация: 21.05.2013 Сообщений: 1,312
	10.11.2013, 15:27 [ТС]
	я тоже не понимаю как? 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.11.2013, 15:28
	попробуйте сдать код из моего последнего комментария. ) мне интересно, что будет. 0

@newyork7776 351 / 344 / 279 Регистрация: 21.05.2013 Сообщений: 1,312
	10.11.2013, 15:30 [ТС]
	пашет 100 балов Добавлено через 7 секунд а мой почему нет? 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.11.2013, 15:33
	потому что разница, которая между ними есть, накладывает отпечаток. это не столь важно. разберитесь, как и почему это работает. динамическое программирование - очень важный метод. 1

@D7ILeucoH 22 / 20 / 5 Регистрация: 29.02.2016 Сообщений: 590
	15.10.2017, 10:58
	Во-первых, ответ не 4, а 2... 0

@DobroAlex Заклинатель змей 705 / 560 / 219 Регистрация: 30.04.2016 Сообщений: 2,605
	15.10.2017, 11:09
	D7ILeucoH, во-первых, это некропостинг 0

@D7ILeucoH 22 / 20 / 5 Регистрация: 29.02.2016 Сообщений: 590
	15.10.2017, 12:02
	Модер, зачем ты удалил моё сообщение!? В этой теме нет правильного ответа! Сам попробуй! Ввод: 5 1 2 3 4 5 Вывод: 9 А надо: 6! 0