Cod sursa(job #482634)

Utilizator cont_de_testeCont Teste cont_de_teste Data 4 septembrie 2010 11:15:20
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 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=1; 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; i; --i)
     {
                bst[i]=min=INF;
                T[i] = -1;
                for(j=i+1; j<=N; ++j)
                {
                           if(A[j]>=A[i])
                            {
                           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);
     printf("%d\n", i);
}