1

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

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

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

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

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

Выведите наибольшее значение суммы.

Получился следующий код

#include <iostream>
#include <vector>
using namespace std;
int dp(vector<int>&les, int k) {
    if (k == 1) {
        return les[0];
    } else if (k == 0) {
        return 0;
    }
    return max(dp(les, k-1) + les[k-1], dp(les, k-2) + les[k-1]);
}

int main() {
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
    }
    cout << dp(lesnica, n);
}

Выдаёт ошибку, что "Программа выполнялась слишком долго и была прервана". Как ускорить?

5
  • ускорить можно то, что выполняется, а тут нужно написать новую программу. 15 мая 2022 в 19:45
  • в компиляторе всё выполняется
    – drbllvn
    15 мая 2022 в 19:47
  • @ARHovsepyan ну так сама программа выполняется, только ускорить её нужно, разве нет?
    – 4500zenja
    15 мая 2022 в 19:48
  • Пожалуйста, исправьте вопрос, чтобы он отражал конкретную проблему с достаточным количеством деталей для возможности дать адекватный ответ. 15 мая 2022 в 20:00
  • @4500zenja, программа выполняться для меня означает, что она выполняет то, что требуется. Но тут не то... И рекурсия не так ощутимо замедлит программу, если ее правильно написать. 15 мая 2022 в 20:24

3 ответа 3

2

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

Я просто добавил мемоизацию; программу на правильность не проверял.

#include <iostream>
#include <vector>
using namespace std;

const int SENTINEL = 10000000; // Указатель, что значение не просчитано
                               // (заведомо невозможное значение)
const int N = 1001;            // Заведомо достаточный размер массива значений

int dps[N];

int dp(const vector<int>&les, int k)
{
    if (dps[k] != SENTINEL) return dps[k];
    if (k == 1) {
        return les[0];
    } else if (k == 0) {
        return 0;
    }
    return dps[k] = max(dp(les, k-1) + les[k-1], dp(les, k-2) + les[k-1]);
}

int main() {
    for(int i = 0; i < N; ++i) dps[i] = SENTINEL; // Инициализация массива
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
    }
    cout << dp(lesnica, n);
}

Для сравнения — на примере из 45 ступенек ваша программа считала примерно 6.5 секунд; моя дала на тех же исходных данных тот же ответ за 14 миллисекунд...

3
  • спасибо большое
    – drbllvn
    16 мая 2022 в 12:30
  • Всё равно будет много вызовов рекурсивной функции. Ведь чтобы выбрать максимум из 2 элементов нужно рекурсивно 2 раза перебрать весь массив с конца до начала. при достаточно большом количестве элементов время опять увеличится и скорее всего произойдет переполнение буфера.
    – DmitryK
    16 мая 2022 в 13:43
  • 1
    @DmitryK Нет, не будет. Если в самом худшем случае в глубину будет 1000 вызовов, то давайте прикинем — локальных переменных нет, переменные-аргументы займут примерно 8 байт на ссылку (в 64-разрядном случае) + 4 байта на int. Плюс еще на вызов... Ну, пусть 42 байта, с запасом — итого 64 байта на один вызов. На 1000 вызовов - 64 Кбайт. При обычном стеке в несколько мегабайт переполнения никакого не будет :) Тормоза же не от глубины рекурсии, а от ее ширины — постоянно вычисляются одни и те же значения...
    – Harry
    16 мая 2022 в 15:45
1

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

Я предлагаю делать все необходимые вычисления с ДП прямо в цикле после ввода очередного элемента вектора — так будет точно следоваться линейное время выполнения. Если что, мы подставляем в дополнительную переменную максимум среди текущего элемента, суммы этого же элемента и прошлого и суммы этого же элемента с позапрошым:

#include <iostream>
#include <vector>

using namespace std;


int main() {
    int n;
    cin >> n;
    vector <int> lesnica(n);
    for (int i = 0; i < n; ++i) {
        cin >> lesnica[i];
        int temp = lesnica[i]; // для нормальной проверки без других заморочек
        if (i > 0) {
            temp = max(temp, lesnica[i] + lesnica[i - 1]);
            if (i > 1) {
                temp = max(temp, lesnica[i] + lesnica[i - 2]);
            }
        }
        lesnica[i] = temp;
    }
    cout << lesnica[n - 1];
}
0
1

Когда Вова стоит на n-ой ступеньке стоимостью c(n) какую максимальную сумму s(n) он может набрать? Если он пришёл с предыдущей ступеньки, c(n) + s(n - 1). Если перепрыгнул через ступеньку, то c(n) + s(n - 2). Нам надо выбрать максимальную сумму, так что:

s(n) = max(c(n) + s(n - 1), c(n) + s(n - 2)) =
= c(n) + max(s(n - 1), s(n - 2))

Начальные условия: s(1) = c(1), s(2) = c(2) + max(s(1), 0).

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

#include <algorithm>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int s1 = 0; // лучшая сумма предыдущей ступеньки
    int s2 = 0; // лучшая сумма предпредыдущей ступеньки
    for (int i = 0; i < n; ++i) {
        int c; // число на следующей ступеньке
        std::cin >> c;
        const int s0 = c + std::max(s1, s2);
        s2 = s1;
        s1 = s0;
    }
    std::cout << s1 << '\n';
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.