Cod sursa(job #2385376)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 21 martie 2019 20:57:19
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int n, a[5005], dp[5005], lg, last = INT_MIN;

void Solve(int dim, int pos)
{
    int cand_pos, cand_nr = INT_MAX;
    for (int i = pos + 1; i <= n; i++)
    {
        if (dp[i] == dim && a[i] >= last)
        {
            if (a[i] < cand_nr)
            {
                cand_nr = a[i];
                cand_pos = i;
            }
        }
    }
    fout << cand_pos << " ";
    last = cand_nr;
    if (dim >= 2)
        Solve(dim - 1, cand_pos);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        dp[i] = 1;
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] <= a[j] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
    }

    for (int i = 1; i <= n; i++)
        lg = max(lg, dp[i]);

    fout << lg << "\n";
    Solve(lg, 0);
    return 0;
}