Cod sursa(job #2240448)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 13 septembrie 2018 14:07:43
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>

FILE *fin = freopen("subsir2.in","r",stdin); FILE *fout = freopen("subsir2.out","w",stdout);

static const int NMAX = 5e3 + 5;

/* ---------- Data -------- */
int n, first;
int v[NMAX], best[NMAX], next[NMAX];
/* ---------- Data -------- */

void ReadInput()
{
    scanf("%d",&n);
    for(int i = 1; i<= n; ++i)
        scanf("%d",&v[i]);
}

void Solve()
{
    int mini = 1e6+5, maxi =0;
    best[n] = 1;
    next[n] = 0;
    for(int i = n-1; i>= 1; i--)
    {
        best[i] = 1;
        next[i] = 0;
        mini = 1e6+5;
        int index = 0;
        for(int j = i + 1; j<= n ; ++j)
        {
            if(v[j] > v[i] && v[j] < mini)
            {
                if(index == 0 || best[j] <= best[index])
                {
                    index = j;
                    best[i] = best[j]+1;
                    next[i] = j;
                }
                mini = v[j];
            }
        }
    }

    return;
}

int getSol()
{
    int mini = v[1];
    int index = 1;
    for(int i = 2; i<= n ; ++i)
    {
        if(v[i] < mini)
        {
            if(best[i] <= best[index])
                index = i;
            mini = v[i];
        }
    }
    return index;

}

void PrintOutput()
{
    int x = getSol();
    printf("%d\n", best[x]);
    while(x)
    {
        printf("%d ",x);
        x = next[x];
    }
    return;
}

int main()
{
    ReadInput();
    Solve();
    PrintOutput();
}