Cod sursa(job #16089)

Utilizator horaxCont de teste horax Data 12 februarie 2007 08:49:00
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>

#define DIM 5001

#define INF 0x3f3f

#define input  "subsir2.in"
#define output "subsir2.out"

int N, A[DIM], bst[DIM], T[DIM], rez = INF, poz, min;
char ok[DIM];

void Citire();
void Rezolva();
void Scrie();

int main()
{
    
    Citire();
    
    Rezolva();
    
    Scrie();
    
    return 0;
}    

void Citire()
{
     int i;
     freopen(input, "r", stdin);
     freopen(output,"w",stdout);
     
     scanf("%d", &N);
     min = INF;
     
     for(i=0; i<N; ++i)
     {
              scanf("%d", A+i);
              if(min<=A[i]) continue;
              ok[i] = 1;
              min = A[i];
     }
}     
     
void Rezolva()
{
     int i, j, min;
     
     for(i=N-1; i>=0; --i)
     {
                bst[i]=min=INF;
                T[i] = -1;
                for(j=i+1; j<N; ++j)
                {
                           if(A[j]<A[i]) continue;
                           if(min>A[j]&&(bst[i]>bst[j]+1||(bst[i]==bst[j]+1&&A[j]<A[T[i]])))
                                   bst[i]=bst[j]+1, T[i] = j;
                           if(min>A[j]) min = A[j];
                }
                if(bst[i]==INF)
                       bst[i] = 1, T[i] = i;
                if(ok[i] && (rez>bst[i]||(rez==bst[i]&&A[i]<A[poz])))
                       rez = bst[i], poz = i;
     }                               
}     
     
void Scrie()
{
     int i;
     printf("%d\n", rez);
     
     for(i=poz;i!=T[i];i=T[i])
          printf("%d ", i+1);
     printf("%d\n", i+1);          
}