Pagini recente » Cod sursa (job #1852486) | Cod sursa (job #2853928) | Cod sursa (job #1218705) | Cod sursa (job #879157) | Cod sursa (job #415301)
Cod sursa(job #415301)
#include<stdio.h>
#include<bitset>
using namespace std;
int a[5005],lg[5005],d[5005],i,j,n,mi=10000000,pozmin;
bitset <5005> fol;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
for(i=n;i>=1;--i)
{
lg[i]=1;
int mar=10000000;
for(j=i+1;j<=n;++j)
{
if(a[i]<=a[j])
{
fol[j]=1;
if(a[j]<mar&&(lg[i]==1||lg[i]>=lg[j]+1))
{
mar=a[j];
lg[i]=lg[j]+1;
d[i]=j;
}
}
}
}
for(i=1;i<=n;++i)
if(!fol[i]&&lg[i]<mi)
{
mi=lg[i];
pozmin=i;
}
else if(!fol[i]&&lg[i]==mi&&a[i]<a[pozmin])
{
mi=lg[i];
pozmin=i;
}
i=pozmin;
printf("%d\n",mi);
while(i)
{
printf("%d ",i);
i=d[i];
}
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}