Cod sursa(job #935440)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 14:46:29
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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);         
}