Pagini recente » Cod sursa (job #2647412) | Cod sursa (job #1588430) | Cod sursa (job #829033) | Cod sursa (job #2175258) | Cod sursa (job #60306)
Cod sursa(job #60306)
#include <cstdio>
#define Nmax 5005
#define INF 0x3f3f3f3f
int n;
int sir[Nmax], d[Nmax], last[Nmax];
void citire()
{
int i;
scanf("%d\n", &n);
for (i = 1; i <= n; ++i)
scanf("%d ", &sir[i]);
}
void scrie(int pos)
{
if (pos)
scrie(last[pos]);
else
return;
printf("%d ", pos);
}
void solve()
{
int i, j, max, best;
for (i = 1; i <= n; ++i)
{
max = -1;
d[i] = INF;
for (j = i - 1; j >= 0; --j)
if (sir[j] <= sir[i] && sir[j] > max)
{
if (d[i] > d[j] + 1)
{
d[i] = d[j] + 1;
last[i] = j;
}
max = sir[j];
}
}
max = -1;
best = n;
for (i = n - 1; i >= 1; --i)
if (sir[i] > max)
{
if (d[i] < d[best])
best = i;
max = sir[i];
}
printf("%d\n", d[best]);
scrie(best);
}
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
citire();
solve();
return 0;
}