Pagini recente » Cod sursa (job #1237754) | Cod sursa (job #3224518) | Cod sursa (job #461092) | Cod sursa (job #2476263) | Cod sursa (job #758158)
Cod sursa(job #758158)
#include <stdio.h>
#include <string.h>
#define Dim 5001
#define INF (1<<31)-1
int v[Dim],d[Dim],use[Dim];
int main()
{
int i,j,N,min,max,pos,p;
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));
min=INF;
d[N]=1;
for(i=N-1;i>0;i--)
{
d[i]=N+1;
min=INF;
for(j=i+1;j<=N;j++)
{
if(v[i]<=v[j]&&min>v[j])
if(d[i]>d[j]+1) d[i]=d[j]+1;
if(v[i]<=v[j])
{
use[j]=1;
if(min>v[j]) min=v[j];
}
}
if(d[i]==N+1) d[i]=1;
}
max=-INF;
for(i=1;i<=N;i++)
if(!use[i])
if(max>d[i]) max=d[i];
pos=INF;
p=INF;
for(i=1;i<=N;i++)
if(!use[i])
if(d[i]==max)
if(p>v[i])
{
p=v[i];
pos=i;
}
freopen("subsir2.out","w",stdout);
printf("%d\n",max);
while(1)
{
printf("%d ",pos);
max--;
min=INF;
p=INF;
for(i=pos+1;i<=N;i++)
{
if(d[i]==max)
if(v[pos]<=v[i]&&(v[i]<v[p]||p==INF)&&v[i]<min)
p=i;
if(v[pos]<=v[i]&&v[i]<min) min=v[i];
}
if(p==INF) break;
pos=p;
}
return 0;
}