Cod sursa(job #1010772)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 15 octombrie 2013 18:07:38
Problema Subsir 2 Scor 63
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,v[5005],b[5005];
void Solve()
{ int i,j,m,mn=0,sol,step,set,res=0,pos,newpos,mx;
   b[n]=1; m=v[n];
   for(i=n-1;i>=1;i--)
   { if (v[i]>m) b[i]=1;
       else
       { sol=n+1; set=0;
     for(j=i+1;j<=n;j++)
      if (v[j]>=v[i])
       { if (!set)
          {sol=min(sol,b[j]+1); set=1; mn=v[j];}
         else
          if (v[j]<mn) {sol=min(sol,b[j]+1); mn=v[j];}
       }
        b[i]=sol;
       }
    m=max(v[i],m);
   }
  mn=1000005;
   res=b[1]; pos=1; mn=v[1];

 for(i=2;i<=n;i++)
   {if (v[i]<mn)
     if (b[i]<res || (b[i]==res && v[i]>v[pos])) {res=b[i]; pos=i;}
    mn=min(mn,v[i]);
   }

  g<<res<<"\n"; g<<pos<<" ";
 for(step=res-1;step>0;step--)
 { set=0;  mx=2147000000;
   for(i=pos+1;i<=n;i++)
    if (v[i]>=v[pos])
    { if (!set)
       { if (b[i]==b[pos]-1 && v[i]<mx)
           { newpos=i; mx=v[i];}
         mn=v[i];
       }
      else
       if (b[i]==b[pos]-1 && v[i]<mn && v[i]<mx)
         {newpos=i; mx=v[i];}
       mn=min(mn,v[i]);
    }
  pos=newpos;
  g<<newpos<<" ";
 }


}
int main()
{ int i,z=0;
     f>>n;
    for(i=1;i<=n;i++)
      f>>v[i];
    Solve();
    return 0;
}