Cod sursa(job #1500727)

Utilizator refugiatBoni Daniel Stefan refugiat Data 12 octombrie 2015 17:06:17
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
const int NMAX=5005;
const int inf=10000000;
int v[NMAX],lg[NMAX],suc[NMAX];
bitset<NMAX> extins;
int main()
{
    ifstream si;
    si.open("subsir2.in");
    ofstream so;
    so.open("subsir2.out");
    int n;
    si>>n;
    int i;
    for(i=1;i<=n;++i)
        si>>v[i];
    int j,k;
    for(i=n;i>0;--i)
    {
        k=inf;
        lg[i]=inf;
        for(j=i+1;j<=n;++j)
        {
            if(k>v[j]&&v[i]<=v[j])
            {
                extins[j]=1;
                k=v[j];
                if(lg[j]+1<lg[i])
                {
                    lg[i]=lg[j]+1;
                    suc[i]=j;
                }
                else
                    if(lg[j]+1==lg[i])
                        if(v[suc[i]]>v[j])
                            suc[i]=j;
            }
        }
        if(lg[i]==inf)
            lg[i]=1;
    }/*
    for(i=1;i<=n;++i)
        cout<<v[i]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<lg[i]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<v[suc[i]]<<' ';
    cout<<'\n';
    for(i=1;i<=n;++i)
        cout<<extins[i]<<' ';
    cout<<'\n';
    */int minn=lg[1],poz=1;
    for(i=2;i<=n;i++)
    {
        if(!extins[i])
        {
            if(minn>lg[i])
            {
                minn=lg[i];
                poz=i;
            }
            else
            {
                if(minn==lg[i])
                {
                    if(v[i]<v[poz])
                        poz=i;
                }
            }
        }
    }
    so<<minn<<'\n';
    while(poz)
    {
        so<<poz<<' ';
        poz=suc[poz];
    }
    so<<'\n';
    return 0;
}