Pagini recente » clasament-arhiva-monthly | Cod sursa (job #1095281) | Cod sursa (job #211605) | Cod sursa (job #2560479) | Cod sursa (job #627959)
Cod sursa(job #627959)
#include <stdio.h>
#define NMAX 5010
#define INF (1<<20)
int A[NMAX], best[NMAX], T[NMAX], ok[NMAX];
int i, min, sol, poz, n;
void solve()
{
int i, j;
sol = INF;
for (i=n-1; i>=0; --i) {
best[i] = min = INF;
T[i] = -1;
for (j=i+1; j<n; ++j) {
if (A[j] < A[i])
continue;
if (A[j] < min && (best[i] > best[j]+1 || (best[i] == best[j] + 1 && A[j] < A[T[i]]))) {
best[i] = best[j] + 1;
T[i] = j;
}
if (A[j] < min)
min = A[j];
}
if (best[i] == INF) {
best[i] = 1;
T[i] = i;
}
if (ok[i] && (sol > best[i] || (sol == best[i] && A[i] < A[poz]))) {
sol = best[i];
poz = i;
}
}
}
void print(int i)
{
printf("%d ", i+1);
if (i == T[i])
return;
print(T[i]);
}
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
int i;
min = INF;
scanf("%d", &n);
for (i=0; i<n; ++i) {
scanf("%d", &A[i]);
if (A[i] >= min)
continue;
min = A[i];
ok[i] = 1;
}
solve();
printf("%d\n", sol);
print(poz);
return 0;
}