Cod sursa(job #580927)

Utilizator AndreiMihuAndrei Mihu AndreiMihu Data 13 aprilie 2011 17:11:58
Problema Subsir 2 Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream.h>
ifstream f("subsir2.in");
ofstream g("subsir2.out");
long long a[5005],p[5005],d[5005],n,i,j,w;
int nr(long 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;
  a[0]=1000000;
  for(i=1;i<=n-1;i++) p[i]=n;
  for(i=n-1;i>=1;i--) for(j=i+1;j<=n;j++) if(a[j]>=a[i]&&p[j]+1<p[i]&&a[j]<a[d[i]]) { p[i]=p[j]+1;
                                                                        d[i]=j;
                                                                       }
                                          else if(a[j]>=a[i]&&p[j]+1==p[i]&&a[j]<a[d[i]]) d[i]=j;
  //for(i=1;i<=n;i++) g<<p[i]<<"*"<<d[i]<<"\n";
  g<<nr(1)<<"\n";
  i=1;
  while(i) { g<<i<<" ";
             i=d[i];
           }
  g<<"\n";
  f.close();
  g.close();
  return 0;
}