Pagini recente » Arhiva de probleme | Cod sursa (job #266507) | Cod sursa (job #1817607) | Cod sursa (job #2482664) | Cod sursa (job #200377)
Cod sursa(job #200377)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long n,v[5010],x[5010],i,j,mx,ant,p[5010],p1[5010],rez,rec[5010],fin[5010],nr,t;
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&v[i]);
v[0]=2000000000;
x[n]=1;
p[n]=n;
//p1[n]=n;
for (i=n-1;i>=1;i--)
{
x[i]=1000000000;
ant=1000000000;
p[i]=i;
for (j=i+1;j<=n;j++)
{
if (v[j]>v[i])
p1[j]=1;
if (v[j]>v[i]&&v[j]<ant)
{
ant=v[j];
if (x[i]==(x[j]+1))
{
// p1[j]=i;
if (v[j]<v[p[i]])
p[i]=j;
}
if (x[i]>x[j]+1)
{
x[i]=x[j]+1;
p[i]=j;
// p1[j]=i;
}
}
}
if (x[i]==1000000000)
x[i]=1;
}
//memset(p1,0,sizeof(p1));
/*for (i=1;i<=n;i++)
// if (p[i]!=i)
p1[p[i]]=1;*/
rez=1000000000;
for (i=1;i<=n;i++)
if (x[i]<rez&&p1[i]==0)
rez=x[i];
printf("%d\n",rez);
/*for (i=1;i<=n;i++)
printf("%d ",x[i]);
printf("\n");
for (i=1;i<=n;i++)
printf("%d ",p[i]);
printf("\n");
*/
for (i=1;i<=n;i++)
{
if ((x[i]==rez)&&(p1[i]==0))
{
nr=1;
t=i;
while (t!=p[t])
{
rec[nr]=t;
t=p[t];
nr++;
}
rec[nr]=t;
}
t=1;
while ((v[rec[t]]==v[fin[t]])&&(t<=rez))
t++;
if (v[rec[t]]<v[fin[t]])
{
for (t=1;t<=rez;t++)
fin[t]=rec[t];
}
}
for (i=1;i<=rez;i++)
printf("%d ",fin[i]);
printf("\n");
return 0;
}