Cod sursa(job #482633)

Utilizator cont_de_testeCont Teste cont_de_teste Data 4 septembrie 2010 11:14:38
Problema Subsir 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
# 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] ) continue ;
                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 ;
}