Cod sursa(job #1659824)

Utilizator horatiudumhoratiu horatiudum Data 22 martie 2016 17:25:45
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 5005
#define inf 2000000
using namespace std;
int n, i, j, nr, v[Nmax], a[Nmax], u[Nmax];
int main()
{
    int minv = inf;
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    scanf("%d", &n);
    for (i = 1;i <= n; ++i)
    scanf("%d", &v[i]);
    v[0] = - inf;
    for (i = n; i >= 0; --i)
    {
        minv = inf;
        a[i] = inf;

        for (j = i + 1;j <= n; ++j)
        if (v[j] < minv && v[j] >= v[i])
        {
            minv = v[j];
            if (a[i] > a[j] + 1)
            {
                a[i] = a[j] + 1;
                u[i] = j;
            }
            else
            if (a[i] == a[j] + 1 && v[j] < v[u[i]])
               u[i] = j;
        }

        if (a[i] == inf)
        {
             a[i] = 1;
             u[i] = i;
        }
    }
    printf("%d\n", a[0] - 1);
    i = 0; nr = a[0] - 1;
    while (u[i] != i)
    {
        -- nr;
        printf("%d ", u[i]);
        i = u[i];
    }
    return 0;
}