Cod sursa(job #1631336)

Utilizator borcanirobertBorcani Robert borcanirobert Data 5 martie 2016 15:06:31
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <stack>
using namespace std;

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

const int MAX = 5005;
int a[MAX];
int N;
int D[MAX];
int t[MAX];
int nmax[MAX];
int nmin[MAX];
stack<int> st1, st2;
int indmin;

void Next( int& i, int st, int dr );

int main()
{
    int i, j;

    fin >> N;
    for ( i = 1; i <= N; i++ )
        fin >> a[i];

    st1.push(N);
    st2.push(N);
    for ( i = N - 1; i >= 1; i-- )
    {
        while ( !st1.empty() && a[st1.top()] > a[i] ) st1.pop();
        if ( !st1.empty() )
            nmin[i] = st1.top();
        st1.push(i);

        while ( !st2.empty() && a[st2.top()] < a[i] ) st2.pop();
        if ( !st2.empty() )
            nmax[i] = st2.top();
        st2.push(i);
    }

    D[N] = 1;
    for ( i = N - 1; i >= 1; i-- )
    {
        if ( nmax[i] == 0 )
            D[i] = 1;
        else
        {
            j = nmax[i];
            D[i] = D[j] + 1;
            t[i] = j;

       //     if ( i == 4 )
         //       fout << "DA";

            for ( Next( j, a[i], a[j] ); j <= N && j != 0; Next( j, a[i], a[j] ) )
                if ( D[j] + 1 < D[i] || ( D[j] + 1 == D[i] && a[j] < a[t[i]] ) )
                    D[i] = D[j] + 1, t[i] = j;
        }
    }

    indmin = 1;
    for ( j = 1; j != 0; j = nmin[j] )
        if ( D[j] <= D[indmin] )
            indmin = j;

    fout << D[indmin] << '\n';

    for ( i = indmin; i != 0; i = t[i] )
        fout << i << ' ';

    fin.close();
    fout.close();
    return 0;
}

void Next( int& i, int st, int dr )
{
    int j = i + 1;

    while ( !( a[j] >= st && a[j] <= dr ) && j <= N )
        j++;

    if ( j <= N )
        i = j;
    else
        i = 0;
}