Pagini recente » Cod sursa (job #1275906) | Cod sursa (job #668431) | Cod sursa (job #1336100) | Cod sursa (job #2754501) | Cod sursa (job #1006745)
#include <cstdio>
using namespace std;
int i, j, n, pos, MIN, v[5001], len_max[5001], next_el[5001];
bool ok[5001];
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%d", &v[i]);
len_max[n] = 1;
for(i=n-1; i>=1; --i)
{
len_max[i] = 0x3f3f3f3f;
MIN = 0x3f3f3f3f;
for(j=i+1; j<=n; ++j)
if( v[j] >= v[i] )
{
ok[j] = 1;
if( v[j] < MIN )
{
MIN = v[j];
if( len_max[j] + 1 < len_max[i] )
{
len_max[i] = len_max[j] + 1;
next_el[i] = j;
}
else if( len_max[j] + 1 == len_max[i] && v[ next_el[i] ] > v[j] )
next_el[i] = j;
}
}
if( len_max[i] == 0x3f3f3f3f)
len_max[i] = 1;
}
pos=1;
for(i=2; i<=n; ++i)
if( !ok[i] )
if ( ( len_max[i] < MIN ) || ( len_max[i] == MIN && v[i] <= v[pos] ) )
pos=i;
printf("%d\n", len_max[pos]);
while( pos )
{
printf("%d ", pos);
pos = next_el[pos];
}
return 0;
}