Pagini recente » Cod sursa (job #3174321) | Cod sursa (job #1844541) | Cod sursa (job #1219642) | Cod sursa (job #1734634) | Cod sursa (job #1010430)
#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;
}