Cod sursa(job #68500)

Utilizator floringh06Florin Ghesu floringh06 Data 28 iunie 2007 11:37:23
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
//100 puncte
using namespace std;

#define MAX_N 5005
#define INF 0x3f3f3f3f

#include <stdio.h>

FILE *fin=fopen("subsir2.in","r"),
     *fout=fopen("subsir2.out","w");
    
int n,i,v[MAX_N];    
int a[MAX_N],t[MAX_N];
//a[i] lungimea celui mai scurt subsir crescator maximal care incepe in i
//t[i] indicele termenului urmator lui i in subsirul care incepe in i - reconsituire
//complexitate n^2 - dinamica 
 
void get_sequence(void)
{
  int i,minvl=INF,min=INF,in=0;
  for (i=1; i<=n; i++)
     if (minvl>v[i])
      {
        if (a[i]==min) 
         if (v[i]<v[in]) in=i;            
        if (a[i]<min) { min=a[i]; in=i;}
        minvl=v[i]; 
      }
  fprintf(fout,"%d\n",min); 
  fprintf(fout,"%d ",in); 
  while (t[in]!=0)  {
   fprintf(fout,"%d ",t[in]);
   in=t[in];
  }
  fprintf(fout,"\n");
}   
 
void solve(void)
{
   int i,j,min,ai,minv; 
   a[n]=1; t[n]=0;
   for (i=n-1; i>=1; i--)
    {
      min=INF; minv=INF; ai=INF;         
      for (j=i+1; j<=n; j++)
       {
          if (v[j]<min && v[j]>=v[i])
           { 
             min=v[j]; 
             if (ai==a[j]) 
              if (v[j]<minv) { t[i]=j; minv=v[j];}
             if (a[j]<ai) 
             { ai=a[j]; t[i]=j; minv=v[j]; } 
           }    
          if ((v[j]<min) && (min!=INF) && (v[j]>=v[i]))
           {
             if (ai==a[j]) 
              if (v[j]<minv) { t[i]=j; minv=v[j]; }                  
             if (ai>a[j]) { t[i]=j; ai=a[j]; minv=v[j];}
           }                   
       }  
      if (ai!=INF) a[i]=ai+1; else { a[i]=1; t[i]=0; }            
	}
   get_sequence();
}    
      
int main()
{
   fscanf(fin,"%d\n",&n);
   for (i=1; i<=n; i++) 
     fscanf(fin,"%d",v+i);
           
   solve();
   
   fclose(fin);
   fclose(fout);
   
   return 0;
}