Pagini recente » Cod sursa (job #966320) | Profil raluca.turcu | Cod sursa (job #1840274) | Cod sursa (job #1948784) | Cod sursa (job #561756)
Cod sursa(job #561756)
#include <stdio.h>
#include <string.h>
#define Dim 5001
#define INF 2147483647
int v[Dim];
struct vector
{
int x,pos,i;
}d[Dim];
int main()
{
int N,i,j,size,pos,min,ok;
freopen("subsir2.in","r",stdin);
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%d",&v[i]);
memset(d,0,sizeof(d));
size=1;
d[N].x=1;
d[N].pos=-1;
d[N].i=-INF;
for(i=N-1;i>0;i--)
{
d[i].x=N+1;
d[i].pos=-1;
d[i].i=-INF;
for(j=i+1;j<=N;j++)
if(v[i]<=v[j])
{
if(d[i].x>d[j].x+1&&v[j]>=d[i].i) d[i].x=d[j].x+1;
d[j].pos=1;
d[i].i=v[j];
ok=1;
}
if(d[i].x==N+1) d[i].x=1;
}
size=N+1;
for(i=1;i<=N;i++)
if(d[i].pos==-1)
if(size>d[i].x) size=d[i].x;
freopen("subsir2.out","w",stdout);
printf("%d\n",size);
pos=0;
ok=0;
while(size)
{
min=INF;
for(i=pos+1;i<=N;i++)
if(ok)
{
if(d[i].x==size)
if(min>v[i])
{
min=v[i];
pos=i;
}
}
else
if(d[i].x==size&&d[i].pos==-1)
if(min>v[i])
{
min=v[i];
pos=i;
}
ok=1;
printf("%d ",pos);
size--;
}
printf("\n");
return 0;
}