Cod sursa(job #1933349)

Utilizator raduzxstefanescu radu raduzx Data 20 martie 2017 17:30:59
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
#define nmax 5010
#define inf 2000000000
int n,v[nmax],i,k,x,cate[nmax],urm[nmax];
bool use[nmax];
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    int j,minim;
    for(i=n;i>=1;i--)
    {
        minim=inf;
        if(i==1)
            j=2;
        for(j=i+1;j<=n;j++)
        {
            if(v[i]<=v[j])
            {
                if(minim>v[j])
                {
                    minim=v[j];
                    use[j]=1;
                    if(!urm[i] or cate[j]+1<cate[i])
                    {
                        cate[i]=cate[j]+1;
                        urm[i]=j;
                    }
                    else
                    {
                        if(cate[j]+1==cate[i] and v[j]<v[urm[i]])
                        {
                            urm[i]=j;
                            cate[i]=cate[j]+1;
                        }
                    }
                }
            }
        }
        if(urm[i]==0)
        {
            cate[i]=1;
        }
    }
    int ok=0;
    minim=inf;
    for(i=1;i<=n;i++)
    {
        if(minim>cate[i] and use[i]==0)
        {
            minim=cate[i];
            ok=i;
        }
        else
            if(minim==cate[i] and use[i]==0)
            {
                if(v[i]<v[ok])
                    ok=i;
            }
    }
    g<<minim<<'\n';
    while(ok)
    {
        g<<ok<<" ";
        ok=urm[ok];
    }
    return 0;
}