Cod sursa(job #1047439)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 4 decembrie 2013 14:47:38
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#define Nmax 5005
#define INF 1000000000

using namespace std;

int N,a[Nmax],lis[Nmax],next[Nmax];
bool bun[Nmax];

inline void Read()
{
    int i;
    ifstream fin("subsir2.in");
    fin>>N;
    for(i=1;i<=N;++i)
        fin>>a[i];
    fin.close();
}

inline void Solve()
{
    int minim,poz,x,y,i,j;

    bun[1]=true;
    minim=a[1];
    for(i=2;i<=N;++i)
        if(a[i]<minim)
        {
            bun[i]=true;
            minim=a[i];
        }

    lis[N]=1; next[N]=0;
    for(i=N-1;i>0;--i)
    {
        x=a[i]; minim=INF; y=INF;
        for(j=i+1;j<=N;++j)
            if(a[j]>=x && a[j]<y)
            {
                y=a[j];
                if(lis[j]<=minim)
                {
                    minim=lis[j];
                    poz=j;
                }
            }
        if(minim==INF)
        {
            lis[i]=1; next[i]=0;
        }
        else
        {
            lis[i]=minim+1;
            next[i]=poz;
        }
    }
    minim=INF;
    for(i=1;i<=N;++i)
        if(bun[i] && lis[i]<minim)
        {
            minim=lis[i];
            poz=i;
        }
    ofstream fout("subsir2.out");
    fout<<minim<<"\n";
    while(poz)
    {
        fout<<poz<<" ";
        poz=next[poz];
    }
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}