Cod sursa(job #1756164)

Utilizator preda.andreiPreda Andrei preda.andrei Data 11 septembrie 2016 23:38:28
Problema Subsir 2 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

#define NMAX 2002
#define INFINIT (1 << 20)

int v[NMAX];
int lmax[NMAX];
int predecesor[NMAX];
bitset<NMAX> continuat;

void afiseazaSir(int i, ofstream &f);
int comparaSiruri(int i1, int i2);

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

    int n;
    fin >> n;

    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        lmax[i] = INFINIT;
    }

    for (int i = 1; i <= n; ++i) {
        int minim = INFINIT;

        if (lmax[i] == INFINIT) {
            lmax[i] = 1;
        }

        for (int j = i + 1; j <= n; ++j) {
            if (minim > v[j] && v[i] <= v[j]) {
                continuat[i] = true;
                if (lmax[i] + 1 < lmax[j]) {
                    lmax[j] = lmax[i] + 1;
                    predecesor[j] = i;
                }
                else if (lmax[i] + 1 == lmax[j] && comparaSiruri(i, predecesor[j]) < 0) {
                    predecesor[j] = i;
                }
            }

            if (v[j] >= v[i])
                minim = min(minim, v[j]);
        }
    }

    int raspuns = INFINIT;
    int index = 0;

    for (int i = 1; i <= n; ++i) {
        if (!continuat[i] && lmax[i] <= raspuns) {
            if (lmax[i] < raspuns) {
                raspuns = lmax[i];
                index = i;
            }
            else if (comparaSiruri(i, index) < 0){
                index = i;
            }
        }
    }

    fout << raspuns << "\n";
    afiseazaSir(index, fout);

    return 0;
}

void afiseazaSir(int i, ofstream &f)
{
    vector<int> indici;
    do {
        indici.push_back(i);
        i = predecesor[i];
    } while (i != 0);

    for (i = indici.size() - 1; i >= 0; --i) {
        f << indici[i] << " ";
    }
}

int comparaSiruri(int i1, int i2)
{
    int comp = (predecesor[i1] == 0) ? 0 : comparaSiruri(predecesor[i1], predecesor[i2]);
    if (comp == 0 && v[i1] != v[i2])
        comp = (v[i1] < v[i2]) ? -1 : 1;
    return comp;

}