Cod sursa(job #214000)

Utilizator katakunaCazacu Alexandru katakuna Data 12 octombrie 2008 14:15:20
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>   
#define MAX 1000011   
  
int e[5111],d[5111],t[5111],sol[5111],p,n,i,v[5111],a[5111],b[5111],j,min;   
  
int cmp(){   
int i;   
  
  for(i=1;i<=min;i++){   
    if( v[d[i]] > v[sol[i]] )   
    return 0;   
  }   
  
return 1;   
}   
  
  
int main(){   
  
FILE *f=fopen("subsir2.in","r");   
FILE *g=fopen("subsir2.out","w");   
  
fscanf(f,"%d",&n);   
  
   for(i=1;i<=n;i++){   
   fscanf(f,"%d",&v[i]);   
   }   
  
v[0]=-MAX;   
int max;   
  
     for(i=1;i<=n;i++)   
     a[i]=MAX;   
  
     for(i=1;i<=n;i++){   
     max=-MAX -1;   
  
      for(j=i-1;j>=0;j--){   
         if(v[i] >= v[j] && v[j] > max){   
         b[j]=1;   
  
            if(a[i] == a[j]+1 && v[j] < v[t[i]] ){   
            a[i] = a[j]+1;   
            t[i]=j;   
            e[i]=1;   
            max=v[j];   
            }   
  
            if(a[i] > a[j]+1){   
            a[i] = a[j]+1;   
            t[i]=j;   
            e[i]=1;   
            max=v[j];   
            }   
               
         }   
  
           if(v[j]<=v[i]&&v[j]>max)   
           max=v[j];   
  
       }   
  
       if(a[i]==MAX)   
       a[i]=1;   
  
  
  
     }   
  
min=5111;   
sol[1]=MAX;   
  
     for(i=1;i<=n;i++){   
       if(!b[i]&&a[i]==min){   
       p=i;   
         for(j=min;j>=1;j--){   
         d[j]=p;   
         p=t[p];   
         }   
  
         if(cmp()){   
            for(j=1;j<=min;j++)   
            sol[j]=d[j];   
         }   
  
       }   
  
       if(!b[i]&&a[i]<min){   
       min=a[i];   
       p=i;   
         for(j=min;j>=1;j--){   
         sol[j]=p;   
         p=t[p];   
         }   
  
       }   
     }   
  
  fprintf(g,"%d\n",min);   
  for(i=1;i<=min;i++)   
  fprintf(g,"%d ",sol[i]);   
  
fclose(f);   
fclose(g);   
  
return 0;   
}