Cod sursa(job #2240447)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 13 septembrie 2018 14:02:39
Problema Subsir 2 Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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];
            }
        }

        if(best[i] >= maxi)
        {
            maxi = best[i];
            first = i;
        }
    }

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

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