Cod sursa(job #581825)

Utilizator AndreiMihuAndrei Mihu AndreiMihu Data 14 aprilie 2011 16:58:37
Problema Subsir 2 Scor 41
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream.h>
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,i,j,a[5005],d[5005],p[5005],min,w;
int nr(int i)
{ if(d[i]==0) return 1;
  return 1+nr(d[i]);
}
int main()
{ f>>n;
  for(i=1;i<=n;i++) f>>a[i];
  p[n]=1;
  d[n]=0;
  for(i=n-1;i>=1;i--) { min=n;
                        j=i+1;
                        while(j<=n&&a[i]>a[j]) j++;
                        if(j<=n) { min=p[j];
								   w=a[j];
                                   d[i]=j;
                                   //g<<w<<" *** ";								   
						           for(j=j+1;j<=n;j++) if(a[j]>=a[i]&&p[j]<min&&a[j]<w) { min=p[j];
										             							          d[i]=j;
								                                                         // g<<a[j]<<"\n";
									  				            			            }
						                                else if(a[j]>=a[i]&&p[j]==min&&a[j]<a[d[i]]) { min=p[j];
											                                                           d[i]=j;
																						             }
						         }
						p[i]=(min+1)%n;
                      }
  g<<nr(1)<<"\n";
  i=1;
  while(i) { g<<i<<" ";
             i=d[i];
           }
  g<<"\n";
  f.close();
  g.close();
  return 0;
}