Cod sursa(job #4428)

Utilizator cos_minBondane Cosmin cos_min Data 3 ianuarie 2007 10:45:07
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "subsir2.in"
#define out "subsir2.out"
#define dim 5001

int v[dim], t[dim], a[dim], sel[dim];
int n;

void ReadData();
void Solve();
int Ok(int,int);
int Real(int);
void Magic(int);

int main()
{
    ReadData();
    Solve();
    
    return 0;
}

void ReadData()
{
     freopen(in,"r",stdin);
     
     scanf("%d",&n);
     for ( int i = 1; i <= n; i++ )
     {
         scanf("%d",v+i);
     }
}

int Ok(int k,int p)
{
    for ( int i = k+1; i < p; i++ )
        if ( v[i] >= v[k] && v[i] <= v[p] ) return 0;
    return 1;
}



int Real(int v)
{
    for ( int i = 1; i < v; i++ )
        if ( a[i] <= a[v] ) return 0;
        
    return 1; 
}

void Magic(int p)
{
     if ( t[p] == p )
     {
          printf("%d ",p);
          return;
     }
     printf("%d ",p);
     Magic(t[p]);
}

void Solve()
{
     freopen(out,"w",stdout);
     
     for ( int i = 1; i < n; i++ ) a[i] = 32001;
     
     a[n] = 1;
     t[n] = n;
     
     for ( int i = n; i >= 1; i-- )
     {
         //a[i] = 1;
         int minim = 32001;
         int poz = i;
         
         for ( int j = i+1; j <= n; j++ )
         {
             if ( !Ok(i,j) ) continue;
             if ( v[i] <= v[j] && a[i] > a[j] + 1 )
             {
                  a[i] = a[j] + 1;
                  poz = j;
                  t[i] = j;
                  minim = 1;
             }
             
         }
         if ( minim == 32001 ) a[i] = 1, t[i] = i;
       /*  if ( minim != 32001 && a[i] > minim )
         {
              a[i] = minim;
              t[i] = poz;
         }
         else
         {
             t[i] = i;
             a[i] = 1;
         }*/
     }
     
     int minim = 32001;
     int poz = 0;
     for ( int i = 1; i <= n; i++ )
     {
       //  printf("%d ", t[i]);
         if ( minim > a[i] && Real(i) ) 
         {
              minim = a[i];
              poz = i;
         }
     }
     printf("%d\n",poz);
     Magic(poz);
}