Cod sursa(job #4049)

Utilizator TabaraTabara Mihai Tabara Data 30 decembrie 2006 09:38:41
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#define INF 0x3f3f //32639
#define val 0xff //255
using namespace std;

#define in "subsir2.in"
#define out "subsir2.out"
#define NMAX 501

int a[NMAX],  best[NMAX], tata[NMAX];
int n, minim, poz, sol;
char ok[NMAX];

void Read();
void Dinamic();
void Write();
void Rec( int );

FILE *fout = fopen( out, "w" );

int main()
{
    Read();
    Dinamic();
    Write();
        
    fclose( fout );
    return 0;
}
    
void Read()
{
     FILE *fin = fopen( in, "r" );
     fscanf( fin, "%d", &n );
     int i;
     minim = INF;
     for ( i = 0; i < n; ++i )
     {
         fscanf( fin, "%d", &a[i] );
         if ( a[i] >= minim ) continue;
         ok[i] = 1;
         minim = a[i];
     }
     fclose( fin );
}

void Dinamic()
{
     int i, j, min;
     sol = INF;
     for ( i = n - 1; i >= 0; --i )
     {
         best[i] = min = INF; tata[i] = -1;
         for ( j = i + 1; j < n; ++j )
         {
             if ( a[j] < a[i] ) continue;
             if ( a[j] < min && (best[i] > best[j] + 1 || (best[i] == best[j] + 1 && a[j] < a[tata[i]])))
             {
                  best[i] = best[j] + 1;
                  tata[i] = j;
             }
             if ( a[j] < min )
                min = a[j];
         }
         if ( best[i] == INF ) //daca nu am gasit nici o pozitia j corespunzatoare 
         {
              best[i] = 1;
              tata[i] = i;
         }
         if ( ok[i] && ( sol > best[i] || ( sol == best[i] && a[i] < a[poz] ) ) )
         {
              sol = best[i];
              poz = i;
         }
     }
}

void Write()
{
     fprintf( fout, "%d\n", sol );
     Rec( poz );
}

void Rec( int i )
{
     fprintf( fout, "%d ", i + 1 );
     if ( i == tata[i] ) return;
     Rec( tata[i] );
}