Cod sursa(job #1756154)

Utilizator preda.andreiPreda Andrei preda.andrei Data 11 septembrie 2016 23:08:15
Problema Subsir 2 Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

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

int v[NMAX];
int lmax[NMAX];
int predecesor[NMAX];
bool incompatibil[NMAX][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];
    }

    for (int i = 1; i < n; ++i) {
        int minim = INFINIT;
        for (int j = i + 1; j <= n; ++j) {
            if (v[i] <= minim && minim <= v[j])
                incompatibil[i][j] = true;
            if (v[j] >= v[i])
                minim = min(minim, v[j]);
        }
    }

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

        for (int j = 1; j < i; ++j) {
            if (!incompatibil[j][i] && v[i] >= v[j]) {
                continuat[j] = true;
                if (lmax[j] + 1 < lmax[i]) {
                    lmax[i] = lmax[j] + 1;
                    predecesor[i] = j;
                }
                else if (lmax[j] + 1 == lmax[i] && v[j] < v[predecesor[i]]) {
                    predecesor[i] = j;
                }
            }
        }

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

    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;
            }
        }
    }

//    cerr << index << "\n";
//    cerr << lmax[index] << "\n";

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

    return 0;
}

void afiseazaSir(int i, ofstream &f)
{
    if (predecesor[i] != 0)
        afiseazaSir(predecesor[i], f);
    f << 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;

}