Cod sursa(job #1502377)

Utilizator mariakKapros Maria mariak Data 14 octombrie 2015 16:40:04
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <algorithm>
#define Dim 5002
#define INF 2000000002


using namespace std;
int n, v[Dim], L[Dim], T[Dim], Min, vj, Sol, poz;
void read()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}
void solve()
{
    int i, j;
    v[0] = -INF;
    for(i = n; i >= 0; -- i)
    {
        if(i == 4)
            i = i;
        Min = INF;
        L[i] = Dim;
        for(j = i + 1; j <= n; ++ j)
        {
            if(v[i] <= v[j] && v[j] < Min)
            {
                Min = min(Min, v[j]);
                if(L[i] == L[j] + 1 && v[T[i]] > v[j])
                    T[i] = j;
                if(L[i] > L[j] + 1)
                {
                    L[i] = L[j] + 1;
                    T[i] = j;
                }
            }
        }
        if (L[i] == Dim)
        {
             L[i] = 1;
             T[i] = i;
        }
    }
}
void write()
{
    int i;
    printf("%d\n", L[0] - 1);
    i = 0;
    while(T[i] != i)
    {
        printf("%d ", T[i]);
        i = T[i];
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}