Cod sursa(job #1766439)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 27 septembrie 2016 22:22:57
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<fstream>
#include<algorithm>
#include<map>

using namespace std;

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

const int nmax = 5005;
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 == n + 1) {
        return ;
    }
    fout << pos << " ";
    afis(r[ 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 mn = inf;
    v[n + 1] = inf - 1;
    for (int i = n; i > 0; -- i) {
        v[ i ] = aux[ v[ i ] ];

        d[ i ] = inf;
        mn = inf;
        for (int j = i + 1; j <= n + 1; ++ j) {
            if (v[ j ] >= v[ i ] && mn > 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;
                }
                mn = v[ j ];
            }
        }
    }

    mn = inf;
    for (int i = 1; i <= n; ++ i) {
        if (mn <= v[ i ]) {
            d[ i ] = inf;
        } else {
            mn = 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;
}