Cod sursa(job #1887613)

Utilizator Athena99Anghel Anca Athena99 Data 21 februarie 2017 18:08:10
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

const int inf= 1<<30;
const int nmax= 5000;

int v[nmax+1], d[nmax+1], p[nmax+1];

int main(  ) {
    int n;
    fin>>n;

    v[0]= -inf;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i];
    }

    for ( int i= n, aux; i>=0; --i ) {
        d[i]= inf, p[i]= i;

        aux= inf;
        for ( int j= i+1; j<=n; ++j ) {
            if ( v[i]<=v[j] && v[j]<aux ) {
                aux= v[j];
                if ( d[j]+1<d[i] || (d[j]+1==d[i] && v[j]<v[p[i]]) ) {
                    d[i]= d[j]+1, p[i]= j;
                }
            }
        }

        if ( d[i]==inf ) {
            d[i]= 1;
        }
    }

    --d[0];
    fout<<d[0]<<"\n";
    for ( int x= 0; x!=p[x]; x= p[x] ) {
        fout<<p[x]<<" ";
    }

    fout<<"\n";

    return 0;
}