Pagini recente » Cod sursa (job #280770) | Cod sursa (job #2712507) | Cod sursa (job #1831793) | Cod sursa (job #690203) | Cod sursa (job #95308)
Cod sursa(job #95308)
#include <stdio.h>
const int N_MAX = 5010;
const int INF = 2000000000;
int v[N_MAX], din[N_MAX], succ[N_MAX];
int main()
{
freopen("subsir2.in", "r", stdin);
#ifndef _SCREEN_
freopen("subsir2.out", "w", stdout);
#endif
int N, i;
scanf("%d\n", &N);
for (i = 1; i <= N; i ++) {
scanf("%d ", &v[i]);
}
int MIN, j;
for (i = N; i >= 1; i --) {
din[i] = INF, succ[i] = i;
MIN = INF;
for (j = i + 1; j <= N; j ++) {
if (v[j] < MIN && v[j] >= v[i]) {
MIN = v[j];
if ((din[j] + 1 < din[i]) || (din[j] + 1 == din[i] && v[j] < v[succ[i]])) {
din[i] = din[j] + 1;
succ[i] = j;
}
}
}
if (din[i] == INF) din[i] = 1;
}
int inc = 0, l = INF;
MIN = INF;
for (i = 1; i <= N; i ++) {
if (v[i] < MIN && din[i] <= l) {
MIN = v[i];
inc = i;
l = din[i];
}
}
printf("%d\n", l);
i = inc;
while (succ[i] != i) {
printf("%d ", i);
i = succ[i];
}
printf("%d\n", i);
return 0;
}