Cod sursa(job #866387)

Utilizator ericptsStavarache Petru Eric ericpts Data 27 ianuarie 2013 22:52:13
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;
int n,logN;
int v[5005];
int best[5005];
int hi;
int st;
int next[5005];

ifstream in("subsir2.in");
ofstream out("subsir2.out");

void cmlsc()
{
    int i,j;
    for(i = n ; i ; -- i)
    {
        best[i] = 1;
        for(j = i + 1 ; j <= n; ++ j)
            if(v[j] > v[i])
                if(best[j] + 1 > best[i] || best[j] + 1 == best[i] && v[j] < v[next[i]])
                {
                    next[i] = j;
                    best[i] = best[j]+1;
                }
        if(best[i] > hi || best[i] == hi && v[i] < v[st])
        {
            st = i;
            hi = best[i];
        }
    }
}

void write()
{
    out << hi << "\n";
    int x = st;
    do
    {
        out << x << " ";
        x = next[x];
    }
    while(x);
}

int main()
{
    int i;
    in >> n;
    for(logN = 1 ; logN < n ; logN <<= 1);
    for(i=1;i<=n;++i)
        in >> v[i];
    cmlsc();
    write();
    return 0;
}