Pagini recente » Istoria paginii runda/anti_avram_1 | Cod sursa (job #1340289) | Cod sursa (job #1278592) | Istoria paginii runda/oji2017simulare | Cod sursa (job #134730)
Cod sursa(job #134730)
#include <stdio.h>
int n, v[5001], best[5001], p[5001], ok[5001], maxim = 10000;
void afis(int i)
{
if (p[i]) afis(p[i]);
printf("%d ",i);
}
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i, j, val;
scanf("%d",&n);
for (i = 1; i <= n; i++) scanf("%d", v + i);
best[1] = 1; ok[1] = 1;
for (i = 2; i <= n; i++)
{
val = - 3000000;
for (j = i - 1; j >= 1; j--)
{
if (v[i] > v[j] && (best[j] + 1 >= best[i]) && ((val < v[j] || v[i] < val) || val == -3000000))
{
best[i] = best[j] + 1;
if (!p[i] || v[j] < v[p[i]]) p[i] = j;
ok[j] = 1;
}
if (v[i] > v[j]) ok[j] = 1;
if (val < v[j]) val = v[j];
}
if (! best[i]) best[i] = 1;
}
for (i = n; i >= 1; i--) if (!ok[i] && best[i] < maxim)
{
maxim = best[i];
val = i;
}
printf("%d\n",maxim);
afis(val);
return 0;
}