Cod sursa(job #16106)

Utilizator raula_sanChis Raoul raula_san Data 12 februarie 2007 09:47:04
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<stdio.h>

#define dim 5005
#define inf 0x3f3f3f3f

long V[dim], Min=inf; int N, A[dim], T[dim], ok[dim];

void read();
void dynamics();
void write();

int main()
{
    read();
    dynamics();
	write();

    return 0;
}

void read()
{
	 freopen("subsir2.in", "r", stdin);
	 scanf("%d", &N);
     
     int i;
     for(i=1; i<=N; ++i)
     {
              scanf("%ld", V+i);
              if(V[i] < Min)
              {
                      Min = V[i];
                      ok[i] = 1;
              }
     }
     
     fclose(stdin);
}

void dynamics()
{
     int i, j, amin; long min;
     A[N] = 1; T[N] = 0;
     
     for(i=N-1; i; --i)
     {
				min = inf;
                amin = N<<1;
                for(j=i+1; j<=N; ++j)
                           if(V[j] <= min && V[j] >= V[i])
                           {
                                   if( A[j]+1 < amin )
                                   {
                                       amin = A[j]+1;
                                       A[i] = A[j]+1;
									   T[i] = j;
                                   }
                                   if(A[j]+1 == amin && V[j] < min)
                                   {
                                           min = V[j];
                                           T[i] = j;
                                   }
                           }
                if( !A[i] )
                {
                    A[i] = 1;
                    T[i] = 0;
                }
     }
}

void write()
{
     freopen("subsir2.out", "w", stdout);

     int i, p, amin = N<<1; Min = inf;
     for(i=1; i<=N; ++i)
              if( ok[i] && A[i] < amin )
              {
                  amin = A[i];
                  Min = V[i];
                  p = i;
              }
              else if( ok[i] && A[i] == amin && V[i] <= Min )
              {
                   Min = V[i];
                   p = i;
              }
     
     printf("%d\n", A[p]);
     while(p)
     {
             printf("%d ", p);
             p = T[p];
     }
     
     fclose(stdout);
}