Cod sursa(job #944221)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 27 aprilie 2013 18:43:36
Problema Subsir 2 Scor 74
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#define In "subsir2.in"
#define Out "subsir2.out"
#define Nmax 5002
using namespace std;
int Lis[Nmax+2],prev[Nmax+2],a[Nmax+2],n,start,L;
///Lis[i] = lungimea minima a subsirului crescator maximal terminat in a[i]bool viz[Nmax+2];
bool viz[Nmax+2];
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,poz,maxx;
    for(i=1;i<=n;i++)
    {
        Lis[i] = poz  = Nmax;
        maxx = 0;//maxx = el. maxim din secventa [j,i)
        for(j=i-1;j;j--)
        {
            if(a[j]<=a[i]&&maxx<a[j])
            {
                if(Lis[i]>Lis[j]+1)
                {
                    Lis[i] = Lis[j]+1;
                    poz = j;
                }
                else
                    if(Lis[i]==Lis[j]+1&&a[j]<a[poz])
                        poz = j;
                viz[j] = true;
            }
            if(a[j]<=a[i] && maxx<a[j])
                maxx = a[j];
        }
        if(Lis[i]==Nmax)
            Lis[i] = 1;
        prev[i] = poz;
    }
    L = Nmax;
    for(i=1;i<=n;i++)
        if(viz[i]==false)
        {
            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;
}