Решение задачи Лесенка-2 с Acmp

Без пояснения   Просмотров: 65


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

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

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n,s = 0;
    cin >> n;
    vector<int> a, temp, path(1 + n);
    for(int i = 0; i < n; ++i){
        cin >> s;
        a.push_back(s);
        path.push_back(0);
    }
    temp.push_back(a[0]);
    temp.push_back(a[1]);
    if(temp[0] >= 0 && temp[1] >= 0)
        temp[1] = temp[0] + temp[1];
 
    for(int i = 2; i < a.size(); ++i){
        if(temp[i - 1] >= temp[i - 2])
            temp.push_back(temp[i - 1] + a[i]);
        else
            temp.push_back(temp[i - 2] + a[i]);
    }
 
    for(int i = temp.size() - 2; i > 0; --i)
        if(temp[i] >= temp[i - 1])
            path[i] = 1;
        else
            path[i-- - 1] = 1;
 
    for(int i = 0; i < a.size() - 1; ++i)
        if(a[i] > 0)
            path[i] = 1;
    if(n == 2){
        if(a[0] >= 0)
            cout << a[0] + a[1] << endl;
        else
            cout <<  a[1] << endl;
    }
    else
        cout << temp [temp.size() - 1] << endl;
    for(int i = 0; i < path.size(); ++i)
        if(path[i])
            cout << i + 1 << ' ';
 
    cout << a.size();
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться