Cod sursa(job #198373)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 10 iulie 2008 18:45:10
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
# include <stdio.h>

using namespace std;

# define IN "subsir2.in"
# define OUT "subsir2.out"
# define MN 5001
# define inf 1000001

int N,i,min,j,mini,poz;
int V[MN];
int Urm[MN];
int L[MN];

int main()
{
    freopen(IN,"r",stdin);
    freopen(OUT,"w",stdout);

    scanf("%d",&N);
    for (i=1; i<=N; ++i) 
      scanf("%d",&V[i]);
      
    L[N] = 1;
    for (i=N-1; i >=1; --i)
      {
         min=inf;
         mini=inf;
         poz=0;
         for (j=i+1; j<=N; ++j)
           if (V[j]>=V[i]&&V[j]<min)
             {
                if (L[j]==mini) poz=j;
                if (L[j]<mini)
                  {
                     poz=j;
                     mini=L[j];
                  }
                min=V[j];
             }
         if (mini==inf) mini=0;
         L[i]=mini+1;
         Urm[i]=poz;    
      }
      
    min=inf;
    mini=inf;
    for (i=1; i<=N; ++i)
      if (V[i]<min)
        {
           if (mini==L[i]&&V[i]<V[poz])
              poz=i;
           if (mini>L[i]) mini=L[i],poz=i;
              min=V[i];
        }
        
    printf("%d\n",mini);
    for (i=1; i<=mini; ++i)
      {
         printf("%d ",poz);
         poz=Urm[poz];
      }
      
    return 0;
}