Pagini recente » Cod sursa (job #3168484) | Cod sursa (job #2489064) | Cod sursa (job #1593427) | template/fmi-no-stress-6/footer | Cod sursa (job #1756154)
#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;
}