Pagini recente » Cod sursa (job #1821376) | Cod sursa (job #1239376) | Cod sursa (job #164934) | Cod sursa (job #1762973) | Cod sursa (job #4795)
Cod sursa(job #4795)
// 76 pcte :))
#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;
}
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] = -1;
bool q = false;
int poz = i;
int minim = 32001;
for ( int j = i+1; j <= n; j++ )
{
if ( v[i] > v[j] ) continue;
if ( (minim > v[j] && a[i] > a[j] + 1 )|| ( a[i] == a[j]+1 && v[j] < v[t[i]] && t[i] != -1) )
{
a[i] = a[j] + 1;
t[i] = j;
q = true;
if ( minim > v[j] ) minim = v[j];
}
}
if ( q == false ) a[i] = 1, t[i] = i;
}
int minim = 32001;
int poz = 0;
for ( int i = 1; i <= n; i++ )
{
if ( minim > a[i] && ok[i] )
{
minim = a[i];
poz = i;
}
else
{
if ( minim == a[i] && ok[i] )
{
if ( v[i] < v[poz] ) poz = i;
else
{
if ( v[i] == v[poz] )
{
for ( int k = poz, w = i; k != t[k]; k = t[k], w = t[w] )
{
if ( v[w] > v[k] )
{
poz = poz;
break;
}
if ( v[w] < v[k] )
{
poz = i;
break;
}
}
}
}
}
}
}
printf("%d\n",minim);
int k;
for ( k = poz; k != t[k]; k = t[k] )
{
printf("%d ",k);
}
printf("%d ",k);
}