Cod sursa(job #1046603)

Utilizator serbanSlincu Serban serban Data 3 decembrie 2013 10:40:42
Problema Subsir 2 Scor 14
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>

using namespace std;

int n,x[101],pozz[101],sis[101],minn,minN;

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];
    sis[n]=1;
    minN=n;
    for(i=n-1;i>=1;i--)
    {
        pozz[i]=0;
        minn=10000;
        for(j=i+1;j<=n;j++)
        {
            if(x[i]<=x[j] && x[j]<minn)
            {
                minn=x[j];
                pozz[i]=j;
            }
        }
        sis[i]=sis[pozz[i]]+1;
        if(sis[i]>minN) minN=sis[i];
    }
    //se calculeaza la lis
    int ok=0;
    for(i=1;i<=n;i++)
    {
        if(sis[i]!=minN)
        {
            ok=0;
            for(j=1;j<i;j++)
                if(x[i]>=x[j])
                    ok=1;
            if(!ok)
                if(sis[i]<minN)
                    minN=sis[i],pozz[0]=i;
        }
    }
    cout<<minN;
    cout<<"\n";
    i=0;
    while(pozz[i]!=0)
    {
        cout<<pozz[i]<<" ";
        i=pozz[i];
    }
    return 0;
}