Pagini recente » Cod sursa (job #177238) | Monitorul de evaluare | Arhiva de probleme | Cod sursa (job #2015198) | Cod sursa (job #393175)
Cod sursa(job #393175)
#include <cstdio>
FILE *in = fopen("subsir2.in","r"), *out = fopen("subsir2.out","w");
const int maxn = 5001;
int n, a[maxn], l[maxn], p[maxn], ok[maxn];
void read()
{
fscanf(in, "%d", &n);
for ( int i = 1; i <= n; ++i )
fscanf(in, "%d", a + i);
}
void go()
{
l[n] = 1;
l[0] = 1 << 30;
int sol = l[0], psol;
for ( int i = n - 1; i; --i )
{
l[i] = 1;
p[i] = 0;
// l[j] minim
int pmin = 0, min = l[0];
for ( int j = i + 1; j <= n; ++j )
{
if ( a[j] > a[i] )
{
if ( a[j] < min )
{
min = a[j];
if ( l[j] <= l[pmin] )
pmin = j;
}
ok[j] = 1;
}
}
if ( !pmin )
continue;
l[i] = l[pmin] + 1;
p[i] = pmin;
}
//printf("%d\n", p[1]);
int maxx = l[0];
for ( int i = 1; i <= n; ++i )
{
if ( !ok[i] )
if ( l[i] < sol || (l[i] == sol && a[i] < maxx) )
{
sol = l[i];
psol = i;
maxx = a[i];
}
// printf("%d %d %d %d %d\n", i, l[i], ok[i], a[i], p[i]);
}
fprintf(out, "%d\n", sol);
for ( int i = psol; i; i = p[i] )
fprintf(out, "%d ", i);
}
int main()
{
read();
go();
return 0;
}