Pagini recente » Istoria paginii utilizator/online-psyholog-zoom-skype-nm | Istoria paginii utilizator/negreteliza | Atasamentele paginii aaaaaa | Profil | Cod sursa (job #204516)
Cod sursa(job #204516)
#include <stdio.h>
#define nmax 5050
#define infinit 5050505
int N, i, uly, val, j, lgm;
int ult[nmax], ans[nmax], A[nmax], max[nmax], scm[nmax];
void recursie(int i)
{
if (ult[i])
recursie(ult[i]);
ans[++ans[0]] = i;
}
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
for (scanf("%d", &N), i = 1; i <= N; scanf("%d", &A[i]), ++i);
for (lgm = infinit, i = 1; i <= N; ++i)
lgm = A[i] < lgm? A[i]: lgm;
for (i = 1; i <= N; A[i++] -= lgm - 1);
for (max[1] = A[1], i = 2; i <= N; ++i)
max[i] = max[i-1] > A[i]? max[i-1]: A[i];
for (i = 1; i <= N; ++i)
{
for (val = -infinit, scm[i] = infinit, j = i-1; j >= 1 && max[j] > val; j--)
if (A[j] <= A[i] && scm[j] + 1 < scm[i] && A[j] > val)
{
scm[i] = scm[j] + 1;
val = A[j];
ult[i] = j;
}
scm[i] = scm[i] == infinit? 1: scm[i];
}
for (max[N] = A[N], i = N-1; i >= 1; i--)
max[i] = max[i+1] > A[i]? max[i+1]: A[i];
for (i = 1, val = lgm = infinit; i <= N; ++i)
if (A[i] > max[i+1] && (scm[i] < lgm || scm[i] == lgm && A[i] <= val))
{
val = A[i];
lgm = scm[i];
uly = i;
}
recursie(uly);
printf("%d\n", ans[0]);
for (i = 1; i < ans[0]; ++i)
printf("%d ", ans[i]);
printf("%d\n", ans[i]);
return 0;
}