Cod sursa(job #1425350)

Utilizator akaprosAna Kapros akapros Data 27 aprilie 2015 12:52:31
Problema Subsir 2 Scor 73
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 5005
#define inf 1 << 17
using namespace std;
int n, i, j, nr, v[Nmax], a[Nmax], u[Nmax];
int main()
{
    int min = 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)
    {
        min = inf;
        a[i] = n + 1;
        for (j = i + 1;j <= n; ++j)
        if (v[j] < min && v[j] >= v[i] && a[j] + 1 <= a[i])
        {
            a[i] = a[j] + 1;
            u[i] = j;
            min = v[j];
        }
        if (a[i] == n + 1)
        {
             a[i] = 1;
             u[i] = i;
        }
    }
    printf("%d\n", a[0] - 1);
    i = 0; nr = 0;
    while (1)
    {
        ++nr;
        printf("%d ", u[i]);
        if (nr == a[0] - 1) break;
        i = u[i];
    }
    return 0;
}