Cod sursa(job #792604)

Utilizator vlad2901Vlad Berindei vlad2901 Data 27 septembrie 2012 22:18:34
Problema Subsir 2 Scor 63
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define NMAX 5000

int a[NMAX], u[NMAX], last[NMAX], l[NMAX];

void print(int poz)
{
    if(poz == -1)
    {
        return;
    }
    print(last[poz]);
    printf("%d ", poz+1);
}

int main()
{
    int n;

    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);


    scanf("%d", &n);

    for(int i=0;i<n;++i)
    {
        scanf("%d", &a[i]);
    }

    memset(last, -1, NMAX);

    for(int i=0;i<n;++i)
    {
        int v = -1000000;
        l[i] = NMAX;

        for(int j=i-1;j>=0;--j)
        {
            if(a[j] < a[i] && a[j] >= v)
            {
                u[j] = 1;
                v = a[j];
                if(l[i] > l[j] + 1)
                {
                    l[i] = l[j] + 1;
                    last[i] = j;
                }
            }
        }
        if(l[i] == NMAX)
        {
            l[i] = 1;
        }
    }

    int min = NMAX, pozmin = -1;

    for(int i=0;i<n;++i)
    {
        if(u[i] == 0 && (min > l[i] || (min == l[i] && pozmin != -1 && a[pozmin] > a[i])))
        {
            min = l[i];
            pozmin = i;
        }
    }

    printf("%d\n", min);

    print(pozmin);

    return 0;
}