Cod sursa(job #1117488)

Utilizator mvcl3Marian Iacob mvcl3 Data 23 februarie 2014 16:20:13
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

#define in "subsir2.in"
#define out "subsir2.out"
#define Max_Size 5009
#define oo 10000000

std :: ifstream f(in);
std :: ofstream g(out);

int N, minim, A[Max_Size], DP[Max_Size], Tata[Max_Size];
bool Viz[Max_Size];

int main() {
    f >> N;
    for(int i = 1; i <= N; ++i) f >> A[i];

    DP[N] = 1;
    for(int i = N - 1; i >= 1; --i) {
        minim = DP[i] = oo;
        Tata[i] = -1;
        for(int j = i + 1; j <= N; ++j) {
            if(A[i] <= A[j] && minim > A[j]) {
                minim = A[j];
                if(DP[i] > DP[j] + 1 || DP[i] == DP[j] + 1 && A[j] < A[ Tata[i] ] )
                    DP[i] = DP[j] + 1, Tata[i] = j;
            }
            if(A[i] <= A[j])    Viz[j] = 1;
        }
        if(DP[i] == oo) DP[i] = 1;
    }

    int beg; minim = oo;
    for(int i = 1; i <= N; ++i)
        if(minim > DP[i] && !Viz[i])    minim = DP[i], beg = i;
        else
        if(minim == DP[i] && !Viz[i] && A[i] < A[beg])  beg = i;

    g << minim << '\n';
    while(minim) {
        g << beg << ' ';
        beg = Tata[beg], --minim;
    }

    g.close();
    return 0;
}