Cod sursa(job #198188)

Utilizator floringh06Florin Ghesu floringh06 Data 9 iulie 2008 13:47:53
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb

 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;  
 }