Cod sursa(job #1676594)

Utilizator preda.andreiPreda Andrei preda.andrei Data 6 aprilie 2016 00:20:10
Problema Subsir 2 Scor 38
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <cstdio>

using namespace std;

int v[5001];
int lungimi[5001];
int pre[5001];
int subsir[5001];
bool eCapat[5001];

int main()
{
    FILE *fin = fopen("subsir2.in", "r");
    FILE *fout = fopen("subsir2.out", "w");

    int n, lmin, poz, k;

    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n; ++i)
        fscanf(fin, "%d", &v[i]);

    lungimi[1] = 1;
    for(int i = 1; i <= n; ++i){
        eCapat[i] = true;
        for(int j = i + 1; j <= n; ++j){
            if(v[i] < v[j]){
                eCapat[i] = false;
                if(lungimi[i] + 1 > lungimi[j] || (lungimi[i] + 1 == lungimi[j] && v[i] < v[pre[j]])){
                    lungimi[j] = lungimi[i] + 1;
                    pre[j] = i;
                }
            }
        }
    }

    poz = lmin = 0;
    for(int i = 1; i <= n; ++i){
        if(eCapat[i] && (poz == 0 || lungimi[i] < lmin || (lungimi[i] == lmin && v[i] < v[poz]))){
            lmin = lungimi[i];
            poz = i;
        }
    }

    fprintf(fout, "%d\n", lmin);

    k = 0;
    while(poz != 0){
        subsir[++k] = poz;
        poz = pre[poz];
    }

    for(int i = lmin; i >= 1; --i)
        fprintf(fout, "%d ", subsir[i]);

    return 0;
}