Cod sursa(job #1046634)

Utilizator serbanSlincu Serban serban Data 3 decembrie 2013 11:42:24
Problema Subsir 2 Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{
    int i,j,poz;
    /*freopen("sis.in","r",stdin);
    freopen("sis.out","w",stdout);
    */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;
        minn2=10000;
        for(j=i+1;j<=n;j++)
        {
            if(x[i]<=x[j] && sis[j]<minn && x[j]<minn2)
            {
                minn=sis[j];
                minn2=x[j];
                xx=j;
            }
        }
        sis[i]=sis[xx]+1;
        if(sis[i]>minN) minN=sis[i];
    }/*
    sis[1]=1;
    minN=n;
    for(i=2;i<=n;i++)
    {
        for(j=i-1;j>=1;j--)
        {
            if(x[i]>x[j] && ]
        }
    }*/
    //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;
            else if(sis[i]==minN)
            {
                if(x[i]<x[xx])
                    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(minN>1 && x[j]<minn)
                    {
                        minn=x[j];
                        i=j;
                    }
                    else if(minN==1)
                    {
                        if(x[j]<=minn)
                        {
                            minn=x[j];
                            i=j;
                        }
                    }
                }
        }
        xx=i;
        cout<<xx<<" ";
        minN--;
    }

    return 0;
}