Cod sursa(job #993308)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 3 septembrie 2013 16:59:38
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int Array[5002],N,MinBest[5002],Succ[5002],Use[5002],Can_maximal[5002];
void read()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
        f>>Array[i];
        Can_maximal[i]=-1000001;
    }
}
void calculate()
{
    int i,min=1000001,poz=0,minres=1000001;
    MinBest[N]=1;
    for(i=N-1;i>=1;i--)
    {
        min=1000001;
        poz=0;
        MinBest[i]=1;
        for(int j=i+1;j<=N;j++)
        {

            if(Array[i]<=Array[j] && min==MinBest[j] && Can_maximal[j]<Array[i])
            {
                if(Array[poz]>Array[j])
                    poz=j;
            }
            if(Array[i]<=Array[j] && min>MinBest[j] && Can_maximal[j]<Array[i])
            {
                MinBest[i]=MinBest[j]+1;
                min=MinBest[j];
                poz=j;
            }
            if(Array[i]<=Array[j])
                Can_maximal[j]=max(Can_maximal[j],Array[i]);
        }
        Succ[i]=poz;
    }
    int start=0;
    for(i=1;i<=N;i++)
    {
        if(Can_maximal[i]==-1000001 && minres==MinBest[i] && Array[start]>Array[i])
            start=i;
        if(Can_maximal[i]==-1000001 && minres>MinBest[i])
            minres=MinBest[i],start=i;
    }

    g<<minres<<"\n";
    for(i=start;i!=0;i=Succ[i])
        g<<i<<" ";
    g<<"\n";
}
int main()
{
    read();
    calculate();
    return 0;
}