Pagini recente » Cod sursa (job #1842283) | Cod sursa (job #940846) | Cod sursa (job #2352106) | Profil analucaana | Cod sursa (job #561743)
Cod sursa(job #561743)
#include <stdio.h>
#include <string.h>
#define Dim 5001
int v[Dim],use[Dim];
struct vector
{
int x,pos;
}d[Dim];
int main()
{
int i,j,N,pos,max,aux;
freopen("subsir2.in","r",stdin);
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%d",&v[i]);
memset(d,0,sizeof(d));
memset(use,0,sizeof(use));
d[N].x=1;
d[N].pos=N+1;
for(i=N-1;i>0;i--)
{
d[i].x=N+1;
d[i].pos=N+1;
for(j=i+1;j<=N;j++)
if(v[i]<=v[j])
{
use[j]=1;
if(d[i].x>d[j].x+1)
{
d[i].x=d[j].x+1;
d[i].pos=j;
}
else
if(d[i].x==d[j].x+1)
if(v[j]<=v[d[i].pos])
d[i].pos=j;
}
}
max=N+1;
pos=N;
for(i=N;i>0;i--)
if(!use[i])
if(d[i].x<max)
{
max=d[i].x;
pos=i;
}
else
if(d[i].x==max)
{
j=i;
aux=pos;
while(v[j]==v[aux]&&j<=N&&aux<=N)
{
j=d[j].pos;
aux=d[aux].pos;
}
if(v[aux]>v[j]) pos=i;
}
freopen("subsir2.out","w",stdout);
printf("%d\n",max);
while(pos<=N)
{
printf("%d ",pos);
pos=d[pos].pos;
}
printf("\n");
return 0;
}