Cod sursa(job #1631382)

Utilizator borcanirobertBorcani Robert borcanirobert Data 5 martie 2016 15:30:11
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 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;
bool c;

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";
            c = false;
            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; )
    {
        if ( D[j] <= D[indmin] )
            indmin = j;

        int ind = j;
        for ( j = j + 1; a[j] >= a[ind] && j <= N; j++ );

        if ( j > N ) j = 0;
    }

    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 )
    {
        if ( st != dr && a[j] == st && !c )
        {
            c = true;
            break;
        }

        j++;
    }

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