Cod sursa(job #944077)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 27 aprilie 2013 12:19:41
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
using namespace std;
int Lis[Nmax],prev[Nmax],a[Nmax],n,start,L;
ofstream g(Out);
inline void Citire()
{
    ifstream f(In);
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i];
    f.close();
}
inline void Afisare(int x)
{
    if(x!=Nmax)
    {
        Afisare(prev[x]);
        g<<x<<" ";
    }
}
inline void Dinamic()
{
    int i,j,maxx,poz;
    for(i=1;i<=n;i++)
    {
        maxx = 0;
        poz = Nmax;
        for(j=1;j<i;j++)
            if(a[j]<=a[i])
            {
                if(Lis[j]>maxx)
                {
                    maxx = Lis[j];
                    poz = j;
                }
                else
                    if(Lis[j]==maxx)
                        if(a[j]<a[poz])
                            poz = j;
            }
        Lis[i] = maxx+1;
        prev[i] = poz;
        if(Lis[i]>L)
        {
            L = Lis[i];
            start = i;
        }
        else
            if(Lis[i]==L && a[i]<a[start])
                start  = i;
    }
    g<<L<<"\n";
    Afisare(start);
    g<<"\n";
    g.close();
}
int main()
{
    Citire();
    Dinamic();
    return 0;
}