Pagini recente » Cod sursa (job #1237148) | Cod sursa (job #1556139) | Cod sursa (job #456224) | Cod sursa (job #1098941) | Cod sursa (job #696691)
Cod sursa(job #696691)
#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];
void rec ( int poz ){
if ( !poz ){
return ;
}
rec(T[poz]);
fprintf(g,"%d ",poz);
}
int main () {
fscanf(f,"%d",&n);
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%d",&v[i]);
}
for ( i = 1 ; i <= n ; ++i ){
D[i] = INF;
int val_max = -INF,val_min = INF;
for ( j = i - 1 ; j >= 1 ; --j ){
if ( v[j] > val_max && v[j] <= v[i] ){
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] > val_max && v[j] <= v[i] ) val_max = v[j];
if ( v[j] < val_min ) val_min = v[j];
}
if ( val_min > v[i] ){
D[i] = 1;
}
}
int sol = INF,u = 0;
int val_max = -INF;
for ( i = n ; i >= 1 ; --i ){
if ( D[i] > val_max ){
if ( D[i] < sol ){
sol = D[i]; u = i;
}
else{
if ( D[i] == sol ){
if ( v[T[i]] < v[u] ){
u = i;
}
}
}
}
if ( v[i] > val_max ){
val_max = v[i];
}
}
fprintf(g,"%d\n",sol);
rec(u);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}