Cod sursa(job #1923065)

Utilizator lulian23Tiganescu Iulian lulian23 Data 10 martie 2017 20:31:51
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 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);
}