# Cod sursa(job #561925)

Utilizator Data 21 martie 2011 22:51:56 Subsir 2 75 cpp done Arhiva de probleme 1.21 kb
``````#include <stdio.h>
#include <string.h>

#define Dim 5001
#define INF ((1<<31)-1)

int v[Dim],use[Dim];

struct vector
{
int x,pos;
}d[Dim];

int main()
{
int N,i,j,min,max,pos,ok,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=INF;
d[i].pos=N+1;
min=INF;
for(j=i+1;j<=N;j++)
{
if(v[i]<=v[j]&&min>v[j])
if(d[i].x>d[j].x+1)
{
d[i].x=d[j].x+1;
d[i].pos=j;
use[j]=1;
}
if(v[i]<=v[j]) use[j]=1;
if(min>v[j]&&v[j]>=v[i]) min=v[j];
}
if(d[i].x==INF) d[i].x=1;
}

max=INF;
pos=0;
for(i=1;i<=N;i++)
if(!use[i])
if(max>d[i].x)
{
max=d[i].x;
pos=i;
}
else
if(max==d[i].x)
if(v[i]<v[pos])
pos=i;

freopen("subsir2.out","w",stdout);

printf("%d\n",max);

while(pos<=N)
{
printf("%d ",pos);
aux=pos;
max--;
ok=1;
min=INF;
pos=N+1;
for(i=aux;i<=N;i++)
{
if(d[i].x==max)
if(min>v[aux]&&(v[pos]>=v[i]||pos==N+1)) pos=i;
if(v[i]>v[aux]&&min>v[i]) min=v[i];
}
}
printf("\n");

return 0;
}
``````