Pagini recente » Cod sursa (job #2171089) | Cod sursa (job #1524954) | Cod sursa (job #1249907) | Cod sursa (job #747047) | Cod sursa (job #1369622)
#include<fstream>
using namespace std;
const int NMAX= 5000, inf= 1000000;
ifstream in( "subsir2.in" );
ofstream out( "subsir2.out" );
int v[NMAX+1], l[NMAX+1], r[NMAX+1];
int main()
{
int N;
in >> N;
for( int i= 1; i<=N; ++i )
{
in >> v[i];
}
++N;
v[0]= -inf;
v[N]= inf;
for( int i= 0; i<=N; ++i )
{
r[i]= -1;
}
for( int i= N-1; i>=0; --i )
{
int mini = inf+1;
l[i]= NMAX+1;
for( int j= i+1; j<=N; ++j )
{
if( ( v[j] >= v[i] ) && ( v[j] < mini ) )
{
if( l[i]-1 > l[j] )
{
l[i]= l[j] + 1;
r[i]= j;
}
else if( l[i]==l[j]+1 && v[i] < v[ r[i] ] )
{
r[i]= j;
}
mini= v[j];
}
}
}
out << l[0]-1 << '\n';
int poz=0;
while( r[poz]!=N )
{
out << r[poz] << ' ';
poz= r[poz];
}
return 0;
}