Cod sursa(job #2129077)

Utilizator papinub2Papa Valentin papinub2 Data 12 februarie 2018 14:40:51
Problema Subsir 2 Scor 49
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 5005;

int main()
{
    int n, start, minim = Nmax + 5;
    vector<int> v(Nmax);
    vector<int> poz(Nmax);
    vector<int> urm(Nmax);
    vector<int> best(Nmax);

    in >> n;

    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
        best[i] = 1;
    }
    poz[n] = -1;

    for (int i = n - 1; i >= 1; i--)
    {
        poz[i] = -1;
        for (int j = i + 1; j <= n; j++)
            if (v[i] < v[j])
            {
                if (best[i] < best[j] + 1)
                {
                    best[i] = best[j] + 1;
                    poz[i] = j;
                }

                else

                if (best[i] == best[j] + 1)
                {
                    if (v[j] < v[poz[i]])
                        poz[i] = j;
                }

                urm[j] = i;
            }
    }

    for (int i = 1; i <= n; i++)
    {
        if (urm[i] == 0 && best[i] < minim)
        {
            minim = best[i];
            start = i;
        }
    }

    out << best[start] << '\n';
    out << start << ' ';

    while (poz[start] != -1)
    {
        out << poz[start] << ' ';
        start = poz[start];
    }

    return 0;
}