Cod sursa(job #1438701)

Utilizator BLz0rDospra Cristian BLz0r Data 20 mai 2015 16:54:55
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
}