Pagini recente » Cod sursa (job #2338084) | Cod sursa (job #1076858) | Cod sursa (job #1699215) | Cod sursa (job #2947624) | Cod sursa (job #203306)
Cod sursa(job #203306)
#include<stdio.h>
#include<stdlib.h>
#define NMAX 5000
#define MMAX 60000
int n,a[NMAX+1];
int M[NMAX+1],nextM[NMAX+1];
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i,j,lmin,ua,max,min,sol[NMAX+1],k,t;
int nrf,first,vfirst,pmin,pmax;
char sir[MMAX],*p;
int ales;
scanf("%d\n",&n);
//for(i=1;i<=n;++i) scanf("%d",&a[i]);
fgets(sir,MMAX,stdin);p=sir;
for(i=1;i<=n;++i){
a[i]=atoi(p);
while(*p!=32) ++p;
++p;
}
min=max=a[1];pmin=pmax=1;
for(i=2;i<=n;++i){
if(a[i]<min) min=a[i],pmin=i;
if(a[i]>=max) max=a[i],pmax=i;
}
if(min==max) {
lmin=n;first=1;
for(i=1;i<=n;++i) sol[i]=i;
goto finish;
}
if(pmin==n) {lmin=1;sol[1]=n; goto finish;}
if(pmax==1) {lmin=1;sol[1]=1; goto finish;}
M[n]=1;
for(i=n-1;i;--i){
lmin=n+1;ua=max+1;
for(j=i+1;j<=n;++j)
if(a[i]<=a[j]){
if(lmin>M[j]&&a[j]<ua){
lmin=M[j];nextM[i]=j;
}
if(lmin==M[j]&&a[j]<ua){
nextM[i]=j;
}
if(ua>a[j]) ua=a[j];
}
if(lmin==n+1) lmin=0;
M[i]=lmin+1;
}
lmin=n+1;ua=max+1;
for(i=1;i<=n;++i){
if(lmin>=M[i]&&a[i]<ua)
{lmin=M[i];first=i;}
if(ua>a[i]) ua=a[i];
}
k=0;
for(i=first;i;){
k++;
sol[k]=i;
i=nextM[i];
}
finish:
printf("%d\n",lmin);
for(i=1;i<=lmin;++i)
printf("%d ",sol[i]);
return 0;
}