Pagini recente » Cod sursa (job #615027) | Cod sursa (job #483076) | Cod sursa (job #2563863) | Cod sursa (job #1103553) | Cod sursa (job #872866)
Cod sursa(job #872866)
#include <cstdio>
#include <fstream>
using namespace std;
const int N = 5001 ;
int n,R;
int A[N],P[N],L[N];
bool C[N];
void READ ()
{
ifstream in ("subsir2.in");
in>>n;
for( int i=1 ; i<=n ; ++i )
{
in>>A[i];
L[i]=N;
}
}
void SOLVE ()
{
L[n]=1;
for( int i=n-1 ; i ; --i )
{
int V=1<<30;
for( int j=i+1 ; j<=n ; ++j )
if( A[i] <= A[j] )
{
if( A[j] < V )
{
if( L[j]+1 < L[i] )
{
L[i]=L[j]+1;
P[i]=j;
}
else
if( L[j]+1 == L[i] && A[j] < A[P[i]] )
P[i]=j;
V=A[j];
}
C[j]=1;
}
}
int V,Lm=N;
for( int i=1 ; i<=n ; ++i )
{
if( C[i] )
continue;
if( L[i] < Lm )
{
Lm=L[i];
V=A[i];
R=i;
}
else
if( L[i] == Lm && A[i] < V )
{
V=A[i];
R=i;
}
}
}
void OUT ()
{
freopen ("subsir2.out","w",stdout);
printf("%d\n",L[R]);
for( ; R ; R=P[R] )
printf("%d ",R);
}
int main ()
{
READ ();
SOLVE ();
OUT ();
return 0;
}