Cod sursa(job #1708338)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 26 mai 2016 22:03:11
Problema Subsir 2 Scor 58
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#define MAXN 5000
#define INF 10000000
int v[MAXN+2],d[MAXN+2],next[MAXN+2],vf[MAXN+2];
int main(){
   FILE*fi,*fout;
   int i,n,j,max,poz,min,minl;
   fi=fopen("subsir2.in" ,"r");
   fout=fopen("subsir2.out" ,"w");
   fscanf(fi,"%d" ,&n);
   for(i=1;i<=n;i++)
      fscanf(fi,"%d" ,&v[i]);
   d[n]=1;
   for(i=n-1;i>0;i--){
       max=0;
       min=INF;
       for(j=i+1;j<=n;j++)
          if(v[i]<v[j]){
            vf[j]=1;
            if(max<d[j]){
               max=d[j];
               next[i]=j;
               min=v[j];
            }
            else
                if(max==d[j]&&min>v[j]){
                   min=v[j];
                   next[i]=j;
                }
          }
       d[i]=max+1;
   }
   minl=INF;
   for(i=1;i<=n;i++)
      if(d[i]<minl&&vf[i]==0)
          minl=d[i];
   min=INF;
   for(i=1;i<=n;i++)
      if(d[i]==minl&&v[i]<min&&vf[i]==0){
         min=v[i];
         poz=i;
      }
   fprintf(fout,"%d\n" ,minl);
   while(poz>0){
      fprintf(fout,"%d " ,poz);
      poz=next[poz];
   }
   fclose(fi);
   fclose(fout);
   return 0;
}