Pagini recente » Cod sursa (job #2269805) | Cod sursa (job #2841558) | Cod sursa (job #1248478) | Cod sursa (job #967489) | Cod sursa (job #49101)
Cod sursa(job #49101)
// Problema Subsir 2
#include <stdio.h>
#define MAX 5001
#define MAXIM 1000001
long s[MAX];
int A[MAX];
int T[MAX];
int M[MAX];
int main()
{
long min = MAXIM;
int pmin = 1;
freopen( "subsir2.in", "rt", stdin );
int n, i;
scanf( "%d", &n );
for( i=1; i<=n; i++ ) { scanf( "%ld", &s[i] ); A[i] = MAX; if( s[i] < min ) { pmin = i; min = s[i]; } }
fclose( stdin );
A[n] = 1;
T[n] = 1;
M[n] = s[n];
int j, p;
int cod;
for( i=n-1; i>=1; i-- )
{
cod = 0;
min = MAXIM;
for( j=i+1; j<=n; j++ )
if( ( s[i] < s[j] ) && ( s[j] < min ) && ( A[i] >= A[j]+1 ) )
{
A[i] = A[j] +1;
if( s[i] < M[j] ) M[i] = s[i]; else M[i] = M[j];
T[i] = j;
min = s[j];
cod = 1;
}
if( !cod )
{
A[i] = 1;
T[i] = i;
M[i] = s[i];
}
}
p = pmin;
int lg = A[p];
freopen( "subsir2.out", "wt", stdout );
printf( "%d\n", lg );
for( i=1; i<lg; i++ ) { printf( "%d ", p ); p = T[p]; }
printf( "%d\n", p );
fclose( stdout );
return 0;
}