Cod sursa(job #1010430)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 14 octombrie 2013 21:01:02
Problema Subsir 2 Scor 62
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 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,set,res=0,pos;
   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);
   }

 sol=b[1]; mn=v[1]; pos=1;

for(i=2;i<=n;i++)
 { if (v[i]<mn)
    { mn=v[i];
      if (b[i]<sol) {sol=b[i]; pos=i;}
    }

 }
g<<sol<<"\n"<<pos<<" ";
set=0; mn=0;
 //for(i=1;i<=n;i++)
  //cout<<b[i]<<" ";
for(i=pos+1;i<=n;i++)
 if (v[i]>=v[pos] && b[i]==(b[pos]-1))
  if (!set || (set && v[i]<mn)) {g<<i<<" "; pos=i; set=0;}

 else
  if (v[i]>=pos)
   if (set) mn=min(mn,v[i]);
    else mn=v[i];

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