Pagini recente » Cod sursa (job #3287051) | Cod sursa (job #114939) | Cod sursa (job #1737377) | Cod sursa (job #41) | Cod sursa (job #4428)
Cod sursa(job #4428)
#include <stdio.h>
#include <fstream>
using namespace std;
#define in "subsir2.in"
#define out "subsir2.out"
#define dim 5001
int v[dim], t[dim], a[dim], sel[dim];
int n;
void ReadData();
void Solve();
int Ok(int,int);
int Real(int);
void Magic(int);
int main()
{
ReadData();
Solve();
return 0;
}
void ReadData()
{
freopen(in,"r",stdin);
scanf("%d",&n);
for ( int i = 1; i <= n; i++ )
{
scanf("%d",v+i);
}
}
int Ok(int k,int p)
{
for ( int i = k+1; i < p; i++ )
if ( v[i] >= v[k] && v[i] <= v[p] ) return 0;
return 1;
}
int Real(int v)
{
for ( int i = 1; i < v; i++ )
if ( a[i] <= a[v] ) return 0;
return 1;
}
void Magic(int p)
{
if ( t[p] == p )
{
printf("%d ",p);
return;
}
printf("%d ",p);
Magic(t[p]);
}
void Solve()
{
freopen(out,"w",stdout);
for ( int i = 1; i < n; i++ ) a[i] = 32001;
a[n] = 1;
t[n] = n;
for ( int i = n; i >= 1; i-- )
{
//a[i] = 1;
int minim = 32001;
int poz = i;
for ( int j = i+1; j <= n; j++ )
{
if ( !Ok(i,j) ) continue;
if ( v[i] <= v[j] && a[i] > a[j] + 1 )
{
a[i] = a[j] + 1;
poz = j;
t[i] = j;
minim = 1;
}
}
if ( minim == 32001 ) a[i] = 1, t[i] = i;
/* if ( minim != 32001 && a[i] > minim )
{
a[i] = minim;
t[i] = poz;
}
else
{
t[i] = i;
a[i] = 1;
}*/
}
int minim = 32001;
int poz = 0;
for ( int i = 1; i <= n; i++ )
{
// printf("%d ", t[i]);
if ( minim > a[i] && Real(i) )
{
minim = a[i];
poz = i;
}
}
printf("%d\n",poz);
Magic(poz);
}