Cod sursa(job #381097)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 8 ianuarie 2010 21:01:12
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#define inf "subsir2.in"
#define outf "subsir2.out"
#define NMax 5001
#define INF 0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N,v[NMax];
int best[NMax],T[NMax];

void Citire()
{
f>>N;
for(int i=1;i<=N;i++)f>>v[i];
}

void Rezolva()
{
int lmin;
int valmin;
int poz;
for(int i=N;i>=1;i--)
    {
    best[i]=1;
    T[i]=i;
    valmin=INF;
    for(int j=i+1;j<=N;j++)
        {
        if(v[j]>=v[i] && v[j]<valmin)
            {
            valmin=v[j];
            if(best[j]+1<best[i]){best[i]=best[j]+1;T[i]=j;}
            else if(best[j]+1==best[i] && v[j]<v[T[i]])T[i]=j;
            }
        }
    }
int max=0;
for(int i=1;i<=N;i++)
    {
    if(best[i]>max){max=best[i];poz=i;}
    }
g<<max<<"\n";
while(1)
    {
    g<<poz<<" ";
    if(T[poz]==poz)break;
    poz=T[poz];
    }
}

int main()
{
Citire();
Rezolva();
f.close();
g.close();
return 0;
}