Cod sursa(job #49101)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 5 aprilie 2007 12:44:28
Problema Subsir 2 Scor 58
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
// 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;
}