Cod sursa(job #1116215)

Utilizator margikiMargeloiu Andrei margiki Data 22 februarie 2014 13:45:56
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
# include <fstream>
# define maxim 10000001
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int a[5005],ver[5005],lung[5005],urm[5005];
int n,i,j,best,poz,Vmin,minn;
int main()
{
    f>>n;
    minn=maxim;
    best=maxim;
    Vmin=maxim;
    for (i=1; i<=n; ++i)
    {
        f>>a[i];
        if (minn>a[i]) minn=a[i],ver[i]=1;
    }
    for (i=n; i>=1; --i)
    {
        lung[i]=maxim; minn=maxim;
        for (j=i+1; j<=n; ++j)
        {
            if (a[j]>=a[i] && a[j]<minn)
            {
                minn=a[j];
                if (lung[i]>lung[j]+1)
                {
                    lung[i]=lung[j]+1;
                    urm[i]=j;
                }
                else if (lung[i]==lung[j]+1 && a[j]<a[urm[i]]) urm[i]=j;
            }
        }
        if (urm[i]==0) lung[i]=1;
        if (ver[i]!=0 && lung[i]<best || lung[i]==best && a[i]<Vmin)
        {
            best=lung[i];
            Vmin=a[i];
            poz=i;
        }
    }
    g<<lung[poz]<<"\n";
    while(poz!=0)
    {
        g<<poz<<" ";
        poz=urm[poz];
    }
    return 0;
}