Pagini recente » Cod sursa (job #763808) | Cod sursa (job #1548990) | Cod sursa (job #907141) | Cod sursa (job #660439) | Cod sursa (job #951753)
Cod sursa(job #951753)
#include <fstream>
#include <iostream>
using namespace std;
#define in "subsir2.in"
#define out "subsir2.out"
#define N 5005
#define oo (1 << 30)
int bst[N], v[N], tata[N], n, MIN = oo, bg;
bool fiu[N];
int main () {
ifstream fin (in);
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> v[i];
bst[i] = 1;
}
v[0] = oo;
bst[0] = oo;
for (int i = n; i; --i) {
for (int j = i + 1; j <= n; ++j)
if (v[i] <= v[j]) {
fiu[j] = 1;
if (v[tata[i]] > v[j] && bst[j] <= bst[tata[i]])
tata[i] = j;
}
if (tata[i])
bst[i] = bst[tata[i]] + 1;
}
for (int i = 1; i <= n; ++i)
if (!fiu[i]) {
MIN = min (MIN, bst[i]);
if (!bg)
bg = i;
}
for (int i = bg + 1; i <= n; ++i)
if (bst[i] == MIN && !fiu[i]) {
int p = i, q = bg;
while (p && q && v[p] > v[q]) {
p = tata[p];
q = tata[q];
}
if (p && q)
bg = i;
}
ofstream fout (out);
fout << MIN << "\n";
while (bg) {
fout << bg << " ";
bg = tata[bg];
}
fout.close();
return 0;
}