Cod sursa(job #1397431)

Utilizator felixiPuscasu Felix felixi Data 23 martie 2015 15:29:36
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int Nmax = 5005;
const int oo = 0x3f3f3f3f;

int N, V[Nmax], Tat[Nmax], Lg[Nmax];

int main()
{
    fin>>N;
    for(int i=1; i<=N; i++)
        fin>>V[i];
    for(int i=N; i; i--)
    {
        Lg[i] = oo; int poz = 0;
        for(int j=i+1; j <= N ;j++)
            if(V[i] <= V[j])
            {
                if(!poz || V[j] < V[poz]) poz = j;
                if(poz && (Lg[poz] + 1 < Lg[i] || (Lg[poz] + 1 == Lg[i] && V[poz] < V[Tat[i]])))
                {
                    Lg[i] = Lg[poz] + 1;
                    Tat[i] = poz;
                }
            }
        if(Lg[i] == oo) Lg[i] = 1;
    }

    int sol = oo, solpoz = 0, poz = 0;
    for(int i=1; i<=N; i++)
    {
        if(!poz || V[poz] > V[i])
        {
            poz = i;
            if(sol > Lg[i] || (sol == Lg[i] && V[i] < V[solpoz]))
            {
                sol = Lg[i];
                solpoz = i;
            }
        }
    }

    fout<<sol<<'\n';
    while(solpoz)
    {
        fout<<solpoz<<' ';
        solpoz = Tat[solpoz];
    }
    return 0;
}