Pagini recente » Cod sursa (job #2716048) | Cod sursa (job #2223734) | Cod sursa (job #2386037) | Cod sursa (job #428030) | Cod sursa (job #482635)
Cod sursa(job #482635)
# include <bitset>
using namespace std ;
const char FIN[] = "subsir2.in",
FOU[] = "subsir2.out" ;
const int MAX = 5005, MOD = 9901, oo = 0x3f3f ;
int A[MAX], best[MAX], father[MAX] ;
int N, sol = oo, psol ;
bitset < MAX > check ;
int main ( void ) {
freopen ( FIN, "r", stdin ) ;
freopen ( FOU, "w", stdout ) ;
scanf ( "%d", &N ) ;
for ( int i = 1, min = oo; i <= N; ++i ) {
scanf ( "%d", A + i ) ;
if ( A[i] < min ) { // searching after minimum
min = A[i] ;
check[i] = 1 ;
}
}
for ( int i = N ; i ; --i ) {
int min = oo ;
best[i] = oo, father[i] = -1 ;
for ( int j = i + 1; j <= N; ++j ) {
if ( A[i] <= A[j] ) {
if ( A[j] < min ) { // if A[j] can be minimum
if ( best[j] + 1 < best[i] || best[i] == best[j] + 1 && A[j] < A[father[i]] ) {
best[i] = best[j] + 1 ; // position found
father[i] = j ;
}
}
if ( A[j] < min ) { // refresh minimum
min = A[j] ;
}
}
}
if ( best[i] == oo ) { // no position found
best[i] = 1 ;
father[i] = i ;
}
if ( check[i] ) {
if ( best[i] < sol || best[i] == sol && A[i] < A[psol] ) {
sol = best[i] ;
psol = i ;
}
}
}
printf ( "%d\n", sol ) ;
for ( int i = psol; i != father[i]; i = father[i] , i == father[i] ? printf ( "%d\n", i ) : 0 ) {
printf ( "%d ", i ) ;
}
if ( psol == father[psol] ) {
printf ( "%d\n", psol ) ;
}
return 0 ;
}