Cod sursa(job #4440)

Utilizator cos_minBondane Cosmin cos_min Data 3 ianuarie 2007 12:32:51
Problema Subsir 2 Scor 51
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 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], ok[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);
     int minim=32001;
     scanf("%d",&n);
     for ( int i = 1; i <= n; i++ )
     {
         scanf("%d",v+i);
         if ( minim <= v[i] ) continue;
         ok[i] = 1;
         minim = 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 ( t[i] == 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 = n; i >= 1; i-- )
     {
         a[i] = 32000, t[i] = i;
         bool q = false;
         int poz = i;
         int minim = 32001;
         
         for ( int j = i+1; j <= n; j++ )
         {
             if ( v[i] > v[j] ) continue;
             if ( ( a[i] > a[j] + 1 && minim > v[j] ) || ( a[i] == a[j]+1 && v[j] < v[t[i]] && t[i] != i ) ) 
             {
                  a[i] = a[j] + 1;
                  t[i] = j;
                  q = true;
                  if ( minim > a[j]) minim = v[j];
             }
             
         }
        // printf("%d ",minim);
         if ( q == false ) a[i] = 1, t[i] = i;
     }
     
     int minim = 32001;
     int poz = 0;
     for ( int i = 1; i <= n; i++ )
     {
        // printf("%d %d\n", a[i], t[i]);
         if ( minim > a[i] && ok[i] ) 
         {
              minim = a[i];
              poz = i;
         }
     }
     printf("%d\n",minim);
     Magic(poz);
}