Pagini recente » Cod sursa (job #962469) | Cod sursa (job #2386500) | Cod sursa (job #1135472) | Cod sursa (job #2941118) | Cod sursa (job #4441)
Cod sursa(job #4441)
#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], ok[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);
int minim=32001;
scanf("%d",&n);
for ( int i = 1; i <= n; i++ )
{
scanf("%d",v+i);
if ( minim <= v[i] ) continue;
ok[i] = 1;
minim = 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 ( t[i] == 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 = n; i >= 1; i-- )
{
a[i] = 32000, t[i] = i;
bool q = false;
int poz = i;
int minim = 32001;
for ( int j = i+1; j <= n; j++ )
{
if ( v[i] > v[j] ) continue;
if ( ( a[i] > a[j] + 1 && minim > v[j] ) || ( a[i] == a[j]+1 && v[j] < v[t[i]] && t[i] != i ) )
{
a[i] = a[j] + 1;
t[i] = j;
q = true;
if ( minim > a[j]) minim = v[j];
}
}
// printf("%d ",minim);
if ( q == false ) a[i] = 1, t[i] = i;
}
int minim = 32001;
int poz = 0;
for ( int i = 1; i <= n; i++ )
{
// printf("%d %d\n", a[i], t[i]);
if ( minim > a[i] && ok[i] )
{
minim = a[i];
poz = i;
}
}
printf("%d\n",minim);
Magic(poz);
}