Pagini recente » Cod sursa (job #1687473) | Cod sursa (job #1471417) | Cod sursa (job #562032) | Cod sursa (job #2139100) | Cod sursa (job #1756164)
#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;
}