Pagini recente » Cod sursa (job #595708) | Cod sursa (job #82162) | Cod sursa (job #1466646) | Cod sursa (job #1835243) | Cod sursa (job #2134410)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,i,j,nr,mx,rz,mn,id,v[5005],pre[5005],lng[5005],da[5005],nu[5005];
bool mxm[5005];
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i];
lng[n+1]=n;
lng[1]=1;
pre[1]=0;
for(i=2;i<=n;i++)
{
id=n+1;
mx=-1000005;
for(j=i-1;j>=1;j--)
{
if(v[j]<=v[i]) mxm[j]=1;
if(v[j]>mx&&v[j]<=v[i])
{
mx=v[j];
if(lng[j]<lng[id]) id=j;
}
}
if(mx!=-1000005)
{
lng[i]=lng[id]+1;
pre[i]=id;
}
else
{
lng[i]=1;
pre[i]=0;
}
}
rz=n;
for(i=1;i<=n;i++)
if(mxm[i]==0)
{
if(lng[i]<rz)
{ rz=lng[i]; mn=1000005; }
if(lng[i]==rz&&v[i]<mn)
{ mn=v[i]; id=i; }
}
fout<<rz<<"\n";
for(i=1;i<=rz;i++)
da[i]=n;
for(i=1;i<=n;i++)
if(mxm[i]==0)
{
id=i;
nr=0;
while(id!=0)
{
nr++; nu[nr]=id;
id=pre[id];
}
bool ok=0;
while(ok==0&&nr>0)
{
if(nu[nr]<da[nr]) ok=1;
if(nu[nr]>da[nr]) ok=-1;
nr--;
}
if(ok==1)
for(j=1;j<=rz;j++)
da[j]=nu[j];
}
for(i=rz;i>=1;i--)
fout<<da[i]<<" ";
}