Pagini recente » Cod sursa (job #3162866) | Cod sursa (job #1898615) | Cod sursa (job #3030853) | Cod sursa (job #2920114) | Cod sursa (job #2816900)
#include <stdio.h>
#define nmax 5005
#define inf 2000000000
int i,n,a[nmax],c[nmax],t[nmax],vmax,vmin,rez,pmin;
int main() {
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = n; i >= 1; i--) {
c[i] = inf;
vmax = inf;
for(int j = i + 1; j <= n; j++) {
if(a[j] < vmax && a[j] >= a[i] && (c[j] + 1 < c[i] || (c[j] + 1 == c[i] && a[t[i]] > a[j]))) {
c[i] = c[j] + 1;
t[i] = j;
}
if(a[j] >= a[i] && a[j] < vmax) vmax = a[j];
}
if(c[i] == inf) {
c[i] = 1;
t[i] = -1;
}
}
vmax = vmin = rez = pmin = inf;
for(int i = 1; i <= n; i++) {
if(a[i] < vmax && (c[i] < rez || (c[i] == rez && a[i] < vmin))) {
rez = c[i];
vmin = a[i];
pmin = i;
}
if(a[i] < vmax) vmax = a[i];
}
printf("%d\n",rez);
while(t[pmin] != -1) {
printf("%d ",pmin);
pmin = t[pmin];
}
printf("%d\n",pmin);
return 0;
}