Pagini recente » Cod sursa (job #2425980) | Cod sursa (job #1049430) | Cod sursa (job #443444) | Cod sursa (job #454004) | Cod sursa (job #696780)
Cod sursa(job #696780)
#include<stdio.h>
#define maxn 5005
#define INF (1<<29)
FILE*f=fopen("subsir2.in","r");
FILE*g=fopen("subsir2.out","w");
int n,i,j;
int v[maxn],T[maxn],D[maxn],m[maxn];
int main () {
fscanf(f,"%d",&n);
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%d",&v[i]);
}
for ( i = n ; i >= 1 ; --i ){
D[i] = INF;
int val_mare_min = INF,val_max = -INF;
for ( j = i + 1 ; j <= n ; ++j ){
if ( v[i] <= v[j] && val_mare_min > v[j] ){
if ( D[i] > D[j] + 1 ){
D[i] = D[j] + 1;
T[i] = j;
}
else{
if ( D[i] == D[j] + 1 ){
if ( v[T[i]] > v[j] ){
T[i] = j;
}
}
}
}
if ( v[j] >= v[i] && v[j] < val_mare_min ) val_mare_min = v[j];
if ( v[j] > val_max ) val_max = v[j];
}
if ( val_max < v[i] ){
D[i] = 1;
}
}
m[0] = INF;
for ( i = 1 ; i <= n ; ++i ){
m[i] = m[i-1];
if ( v[i] < m[i] ) m[i] = v[i];
}
int sol = INF,u = 0;
for ( i = n ; i >= 1 ; --i ){
if ( v[i] < m[i-1] ){
if ( D[i] < sol ){
sol = D[i]; u = i;
}
else{
if ( D[i] == sol ){
if ( v[i] < v[u] ){
u = i;
}
}
}
}
}
fprintf(g,"%d\n",sol);
for ( ; u ; u = T[u] ){
fprintf(g,"%d ",u);
}
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}