Pagini recente » Cod sursa (job #2803497) | Cod sursa (job #2678302) | Cod sursa (job #2811980) | Cod sursa (job #2769721) | Cod sursa (job #60313)
Cod sursa(job #60313)
#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 != n + 1)
{
printf("%d ", pos);
scrie(last[pos]);
}
else
return;
}
void solve()
{
int i, j, min, best;
sir[n + 1] = INF - 1;
for (i = n; i >= 1; --i)
{
min = INF;
d[i] = INF;
for (j = i + 1; j <= n + 1; ++j)
if (sir[j] >= sir[i] && sir[j] < min)
{
if (d[i] >= d[j] + 1)
{
d[i] = d[j] + 1;
last[i] = j;
}
min = sir[j];
}
}
min = INF;
best = 1;
for (i = 1; i <= n; ++i)
if (sir[i] < min)
{
if (d[i] >= d[best])
best = i;
min = 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;
}