Pagini recente » Cod sursa (job #69749) | Cod sursa (job #1454554) | Cod sursa (job #812856) | Cod sursa (job #1769738) | Cod sursa (job #755879)
Cod sursa(job #755879)
#include <cstdio>
#define DMAX 5005
struct bestmin {
int b, m; // b - best, m - min
};
bestmin best [DMAX];
int pre [DMAX], v [DMAX], sol [DMAX];
void makesol (int pozmaxx) {
for (; pozmaxx; pozmaxx = pre [pozmaxx])
sol [++ sol [0]] = pozmaxx;
}
int main () {
freopen ("subsir2.in", "r", stdin);
freopen ("subsir2.out", "w", stdout);
int n, i, j, maxx, pozmaxx, minn, minn2;
scanf ("%d", &n);
for (i = 1; i <= n; ++ i) {
scanf ("%d", &v [i]);
best [i] . m = 1000005;
minn2 = 1000005;
maxx = 0;
pozmaxx = 0;
for (j = i - 1; j; -- j) {
if (v [j] <= v [i])
if ((best [j] . b > maxx) || (best [j] . b == maxx && v [j] < best [i] . m) || (best [j] . b == maxx && v [j] == best [i] . m && v [j] < minn2)) {
maxx = best [j] . b;
pozmaxx = j;
minn2 = v [j];
best [i] . m = v [j];
}
}
best [i] . b = maxx + 1;
pre [i] = pozmaxx;
}
maxx = 0; minn = 1000005; minn2 = 1000005;
for (i = 1; i <= n; ++ i) {
if( (best [i] . b > maxx) || (best [i] . b == maxx && best [i] . m < minn) || (best [i] . b == maxx && best [i] . m == minn && v [i] < minn2)) {
maxx = best [i] . b;
minn = best [i] . m;
pozmaxx = i;
minn2 = v [pozmaxx];
}
}
makesol (pozmaxx);
printf ("%d\n", maxx);
for (i = sol [0]; i; -- i)
printf ("%d ", sol [i]);
}