Pagini recente » Cod sursa (job #2601707) | Cod sursa (job #2200070) | Cod sursa (job #1387272) | Cod sursa (job #1852409) | Cod sursa (job #203142)
Cod sursa(job #203142)
#include <stdio.h>
#include <string.h>
const int inf = 1000001;
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
int n, l[5001], r[5001], next[5001], v[5001];
int i, j, min, max;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
{
l[i] = r[i] = inf;
}
v[0] = inf;
memset(next, 0, sizeof(next));
for(i = 1; i <= n; ++i)
{
scanf("%d", &v[i]);
}
for(i = 1; i <= n; ++i)
{
max = -inf;
for(j = i - 1; j > 0; --j)
{
if(v[j] <= v[i])
{
if(v[j] > max)
{
max = v[j];
if(l[j] + 1 < l[i])
{
l[i] = l[j] + 1;
}
}
}
}
if(l[i] == inf)
{
l[i] = 0;
}
}
for(i = n; i > 0; --i)
{
min = inf;
for(j = i + 1; j <= n; ++j)
{
if(v[j] >= v[i])
{
if(v[j] < min)
{
min = v[j];
if(r[j] + 1 < r[i] || (r[j] + 1 == r[i] && v[next[i]] > v[j]))
{
r[i] = r[j] + 1;
next[i] = j;
}
}
}
}
if(r[i] == inf)
{
r[i] = 0;
}
}
int sol = inf, pos;
for(i = 1; i <= n; ++i)
{
if(l[i] == 0)
{
if(l[i] + r[i] < sol || (l[i] + r[i] == sol && v[i] < v[pos]))
{
sol = l[i] + r[i];
pos = i;
}
}
}
printf("%d\n", sol + 1);
while(pos)
{
printf("%d ", pos);
pos = next[pos];
}
printf("\n");
return 0;
}