329 Лесенка 2 - Динамика

// Условие: https://acmp.ru/index.asp?main=task&id_task=329
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//int d[1001], way[1000];

int main()
{
    int n;
    cin >> n;
    vector<int> d(n + 1, 0), f(n+1, 0), way(n, 0);
    for (int i = 1; i <= n; ++i)
    {
        cin >> d[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        f[i] = (i != 1)? max(f[i - 1], f[i - 2]) + d[i] : d[i];
    }

    int k = n, i = 0;
    while (k > 0)
    {
        way[i++] = k;
        if (f[k] == f[k - 1] + d[k])
            k -= 1;
        else
            k-=2;
    }

    cout << f[n] << endl;
    for (int j = i - 1; j >= 0; --j)
    {
        cout << way[j] << ' ';
    }

    return 0;
}