Pagini recente » Cod sursa (job #601971) | Cod sursa (job #3286239) | Cod sursa (job #2854544) | Cod sursa (job #2723326) | Cod sursa (job #2240448)
#include <cstdio>
FILE *fin = freopen("subsir2.in","r",stdin); FILE *fout = freopen("subsir2.out","w",stdout);
static const int NMAX = 5e3 + 5;
/* ---------- Data -------- */
int n, first;
int v[NMAX], best[NMAX], next[NMAX];
/* ---------- Data -------- */
void ReadInput()
{
scanf("%d",&n);
for(int i = 1; i<= n; ++i)
scanf("%d",&v[i]);
}
void Solve()
{
int mini = 1e6+5, maxi =0;
best[n] = 1;
next[n] = 0;
for(int i = n-1; i>= 1; i--)
{
best[i] = 1;
next[i] = 0;
mini = 1e6+5;
int index = 0;
for(int j = i + 1; j<= n ; ++j)
{
if(v[j] > v[i] && v[j] < mini)
{
if(index == 0 || best[j] <= best[index])
{
index = j;
best[i] = best[j]+1;
next[i] = j;
}
mini = v[j];
}
}
}
return;
}
int getSol()
{
int mini = v[1];
int index = 1;
for(int i = 2; i<= n ; ++i)
{
if(v[i] < mini)
{
if(best[i] <= best[index])
index = i;
mini = v[i];
}
}
return index;
}
void PrintOutput()
{
int x = getSol();
printf("%d\n", best[x]);
while(x)
{
printf("%d ",x);
x = next[x];
}
return;
}
int main()
{
ReadInput();
Solve();
PrintOutput();
}