Pagini recente » Cod sursa (job #3236474) | Cod sursa (job #2106941) | Cod sursa (job #2772002) | Cod sursa (job #296473) | Cod sursa (job #7629)
Cod sursa(job #7629)
#include <stdio.h>
#define MAX 5001
#define INF 0x3f3f
int n;
int a[MAX], best[MAX], t[MAX];
int rez = INF;
int poz, minim;
char ok[MAX];
void Read()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
int i;
scanf("%d", &n);
minim = INF;
for (i = 0; i < n; i++)
{
scanf("%d", a + i);
if (minim <= a[i]) continue;
ok[i] = 1;
minim = a[i];
}
}
int main()
{
int i, j, minim;
Read();
for (i = n - 1; i >= 0; i--)
{
best[i] = minim = INF;
t[i] = -1;
for (j = i + 1; j < n; j++)
{
if (a[j] < a[i]) continue;
if (minim > a[j] && (best[i] > best[j] + 1 || (best[i] == best[j] + 1 && a[j] < a[t[i]])))
{
best[i] = best[j] + 1;
t[i] = j;
}
if (minim > a[j]) minim = a[j];
}
if (best[i] == INF)
{
best[i] = 1;
t[i] = i;
}
if (ok[i] && (rez > best[i] || (rez == best[i] && a[i] < a[poz])))
{
rez= best[i];
poz = i;
}
}
printf("%d\n", rez);
for (i = poz; i != t[i]; i = t[i])
printf("%d ", i + 1);
printf("%d\n", i + 1);
return 0;
}