Cod sursa(job #1766367)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 27 septembrie 2016 21:25:44
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<algorithm>
#include<map>

using namespace std;

ifstream fin ("subsir2.in"); ofstream fout ("subsir2.out");

const int nmax = 5000;
const int inf = 1 << 30;
int n;
int v[nmax + 1], d[nmax + 1], r[nmax + 1];

map< int, int > aux;

void afis (int pos) {
    if (pos == 0) {
        return ;
    }
    afis(r[ pos ]);
    fout << pos << " ";
}
int main() {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> v[ i ];
        aux[ v[ i ] ] = 0;
    }

    int ind = 1;
    for (map< int, int >::iterator it = aux.begin(); it != aux.end(); ++ it) {
        it -> second = ind ++;
    }

    int mx = -inf;
    for (int i = 1; i <= n; ++ i) {
        v[ i ] = aux[ v[ i ] ];

        d[ i ] = inf;
        mx = -inf;
        for (int j = i - 1; j >= 0; -- j) {
            if (v[ j ] <= v[ i ] && mx < v[ j ]) {
                if (d[ i ] > d[ j ] + 1 || (d[ i ] == d[ j ] + 1 && v[ j ] < v[ r[ i ] ])) {
                    d[ i ] = d[ j ] + 1;
                    r[ i ] = j;
                }
                mx = v[ j ];
            }
        }
    }

    mx = -inf;
    for (int i = n; i > 0; -- i) {
        if (mx >= v[ i ]) {
            d[ i ] = inf;
        } else {
            mx = v[ i ];
        }
    }

    int sol = 1;
    for (int i = 2; i <= n; ++ i) {
        if (d[ i ] < d[ sol ] || (d[ i ] == d[ sol ] && v[ sol ] > v[ i ])) {
            sol = i;
        }
    }

    fout << d[ sol ] << "\n";
    afis( sol );

    fin.close();
    fout.close();
    return 0;
}