Pagini recente » Cod sursa (job #677951) | Cod sursa (job #1530543) | Cod sursa (job #1457379) | Cod sursa (job #1702843) | Cod sursa (job #982857)
Cod sursa(job #982857)
#include<stdio.h>
int v[5002],a[5002],t[5002],f[5002];
void afis(int i)
{
if(t[i])
afis(t[i]);
printf("%d ",i);
}
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int n,i,j,m,sol,s;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&v[i]);
for(i=1;i<=n;++i)
{
m=-2000000000;
a[i]=2000000000;
for(j=i-1;j>0;--j)
{
if(v[j]<v[i])
{
if(v[j]>m&&(a[j]<a[i]-1||(a[j]==a[i]-1&&v[j]<v[t[i]])))
{
t[i]=j;
f[j]=i;
a[i]=a[j]+1;
}
if(f[j]==0)
f[j]=i;
}
if(v[j]>m&&v[j]<v[i])
m=v[j];
}
if(a[i]==2000000000)
a[i]=1;
}
sol=s=2000000000;
for(i=1;i<=n;++i)
if(f[i]==0&&(a[i]<sol||(a[i]==sol&&v[i]<v[s])))
{
s=i;
sol=a[i];
}
/*for(i=1;i<=n;++i)
printf("%2d ",a[i]);printf("\n");
for(i=1;i<=n;++i)
printf("%2d ",t[i]);printf("\n");
for(i=1;i<=n;++i)
printf("%2d ",f[i]);printf("\n");
printf("\n");*/
printf("%d\n",sol);
afis(s);
printf("\n");
return 0;
}