Pagini recente » Cod sursa (job #1000113) | Cod sursa (job #2568281) | Cod sursa (job #2600998) | Cod sursa (job #2363661) | Cod sursa (job #951760)
Cod sursa(job #951760)
#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])
if (bst[i] < MIN || (bst[i] == MIN && v[bg] > v[i])) {
bg = i;
MIN = bst[i];
}
ofstream fout (out);
fout << MIN << "\n";
while (bg) {
fout << bg << " ";
bg = tata[bg];
}
fout.close();
return 0;
}