Cod sursa(job #1504619)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 17 octombrie 2015 23:06:47
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
/*
    Solutie O(N^2/2)

    pt fiecare i de la N la 1:
        pt fiecare j de la i+1 la N:
            determin D[i] in functie de D[j];
        daca nu am determinat D[i]:
            initializez D[i] cu 1;
*/
#include <cstdio>
#include <algorithm>

#define DIM 5010
#define INF 2000000000
using namespace std;

int N, i, position, maxim, D[DIM], V[DIM], T[DIM];

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

    scanf ("%d", &N);
    for (int i = 1; i <= N; i ++)
        scanf ("%d", &V[i]);
    V[0] = -INF;

    for (int i = N; i >= 0; i --)
    {
        int vmin = INF; D[i] = INF;
        for (int j = i + 1; j <= N; j ++)
        {
            if (V[j] < vmin && V[j] >= V[i])
            {
                vmin = min (vmin, V[j]);

                if (D[i] == D[j] + 1 && V[T[i]] > V[j])
                    T[i] = j;

                if (D[i] > D[j] + 1)
                {
                    D[i] = D[j] + 1;
                    T[i] = j;
                }
            }

            if (V[j] >= V[i] && vmin > V[j])
                vmin = V[j];
        }

        if (D[i] == INF)
        {
            D[i] = 1;
            T[i] = i;
        }
    }

    printf ("%d\n", D[0] - 1);

    position = 0;
    while (T[position] != position)
    {
        printf ("%d ", T[position]);
        position = T[position];
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}