Pagini recente » Cod sursa (job #1306169) | Cod sursa (job #1568834) | Cod sursa (job #3137463) | Cod sursa (job #643088) | Cod sursa (job #1438701)
#include <cstdio>
using namespace std;
#define Nmax 5002
#define inf 0x3f3f3f3f
FILE *f = fopen ( "subsir2.in", "r" );
FILE *g = fopen ( "subsir2.out", "w" );
int v[Nmax], D[Nmax], pred[Nmax];
int main(){
int N;
fscanf ( f, "%d", &N );
for ( int i = 1; i <= N; ++i )
fscanf ( f, "%d", &v[i] );
int minv;
for ( int i = N; i >= 1; --i ){
D[i] = minv = inf;
for ( int j = i + 1; j <= N; ++j ){
if ( v[j] < minv && v[i] <= v[j] ){
minv = v[j];
if ( D[i] > D[j] + 1 || ( D[i] == D[j] + 1 && v[pred[i]] > v[j] ) ){
D[i] = D[j] + 1;
pred[i] = j;
}
}
}
if ( D[i] == inf ){
D[i] = 1;
pred[i] = -1;
}
}
int vmax, vmin, rez, pmin;
vmax = vmin = rez = pmin = inf;
for( int i = 1; i <= N; ++i ){
if ( v[i] < vmax ){
vmax = v[i];
if ( D[i] < rez || ( D[i] == rez && v[i] < vmin ) ){
rez = D[i];
vmin = v[i];
pmin = i;
}
}
}
fprintf ( g, "%d\n", rez );
while( pmin != -1 ){
fprintf ( g, "%d ", pmin );
pmin = pred[pmin];
}
return 0;
}