Cod sursa(job #381090)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 8 ianuarie 2010 20:37:32
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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;
    lmin=valmin=INF;
    for(int j=i+1;j<=N;j++)
        {
        if(v[j]>=v[i] && best[j]<lmin)
            {
            if(v[j]<valmin)
                {
                lmin=best[j];
                valmin=v[j];
                poz=j;
                }
            }
        else if(best[j]==lmin && v[j]<valmin)
            {
            valmin=v[j];
            poz=j;
            }
        }
    if(lmin==INF){best[i]=1;T[i]=i;}
    else {best[i]=lmin+1;T[i]=poz;}
    }
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;
}