Cod sursa(job #1046614)

Utilizator serbanSlincu Serban serban Data 3 decembrie 2013 11:08:40
Problema Subsir 2 Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>

using namespace std;

int n,x[5001],pozz[5001],sis[5001],minn,minN,maxx,xx;

int main()
{
    int i,j,poz;
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i];
        if(x[i]>maxx) maxx=x[i];
    }
    sis[n]=1;
    minN=n;
    for(i=n-1;i>=1;i--)
    {
        xx=0;
        minn=10000;
        for(j=i+1;j<=n;j++)
        {
            if(x[i]<=x[j] && x[j]<minn)
            {
                minn=x[j];
                xx=j;
            }
        }
        sis[i]=sis[xx]+1;
        if(sis[i]>minN) minN=sis[i];
    }
    //se calculeaza la lis
    int ok=0;
    for(i=1;i<=n;i++)
    {
        ok=0;
        for(j=1;j<i;j++)
            if(x[i]>=x[j])
                ok=1;
        if(!ok)
            if(sis[i]<minN)
                minN=sis[i],xx=i;
    }
    cout<<minN;
    cout<<"\n";
    cout<<xx<<" ";
    minN--;
    while(minN>0)
    {
        minn=maxx;
        for(j=xx+1;j<=n;j++)
        {
            if(x[j]>x[xx])
                if(sis[j]==sis[xx]-1)
                {
                    if(x[j]<minn)
                    {
                        minn=x[j];
                        i=j;
                    }
                }
        }
        xx=i;
        cout<<xx<<" ";
        minN--;
    }

    return 0;
}