Pagini recente » Cod sursa (job #2707735) | Cod sursa (job #1010772)
#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;
}