Pagini recente » Istoria paginii template/happy-birthday-2014/footer | Cod sursa (job #2861082) | Istoria paginii utilizator/szasz1alex2 | Istoria paginii runda/tsa_ojisim2014 | Cod sursa (job #319292)
Cod sursa(job #319292)
#include<stdio.h>
#define inf 0x3f3f
int n,poz,min,rez=inf;
int v[5005];
int pred[5005];
int ok[5005];
int sol[5005];
void read()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
min=inf;
int i;
for(i=0;i<n;i++)
{
scanf("%d",&v[i]);
if(min<=v[i])
continue;
ok[i]=1;
min=v[i];
}
}
void rezx()
{
int i,j,min;
for(i=n-1;i>=0;i--)
{
sol[i]=min=inf;
pred[i]=-1;
for(j=i+1;j<n;j++)
{
if(v[j]<v[i])
continue;
if(min>v[j] && (sol[i]>sol[j]+1 || (sol[i]==sol[j]+1 && v[j]<v[pred[i]])))
{
sol[i]=sol[j]+1;
pred[i]=j;
}
if(min>v[j])
min=v[j];
}
if(sol[i]==inf)
{
sol[i]=1;
pred[i]=i;
}
if(ok[i] && (rez>sol[i] || (rez==sol[i] && v[i]<v[poz])))
{
rez=sol[i];
poz=i;
}
}
printf("%d\n",rez);
for(i=poz;i!=pred[i];i=pred[i])
printf("%d ",i+1);
printf("%d\n",i+1);
}
int main()
{
read();
rezx();
return 0;
}