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 that you have read and understand our privacy policy and code of conduct.

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