Cod sursa(job #1237302)

Utilizator lucian666Vasilut Lucian lucian666 Data 3 octombrie 2014 19:08:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb


#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>


#define NN 100009
using namespace std;
ofstream out("scmax.out");

int dp[NN] , v[NN] , poz[NN];
int p , mmax , n ;

void Read();
void Scm();
void Write();

int main()
{

    Read();
    Scm();
    Write();

    return 0;


}

void Read()
{

    ifstream in("scmax.in");

    in >> n;

    for( int i = 1; i<=n ; i++)
        in >> v[i];

}

void Scm()
{

    /*
    dp[1] = 1;
    poz[1] = -1;
    mmax = -1;
    p = n;
    for( int i = 2 ; i <=n  ; i++ )
    {

        dp[i] = 1;
        poz[i] = -1;
        for( int j = 1 ; j < i  ; ++j )
            if( v[i] > v[j] )
                if( dp[i] < dp[j] + 1 )
                {

                    dp[i] = dp[j] + 1;
                    poz[i] = j;
                    if( dp[i] > mmax  )
                        mmax = dp[i] , p = i;

                }
    }

    */

    dp[n] = 1;
    poz[n] = -1;

    mmax = -1;
    p = n;

    for( int i = n - 1; i >=1 ; --i )
    {

        dp[i] = 1;
        poz[i] = -1;

        for( int j = i + 1 ; j<=n ; ++j )
            if( v[i] < v[j] )
                if( dp[i] < dp[j] + 1 )
                {

                    dp[i] = dp[j] + 1;
                    poz[i] = j;
                    if( dp[i] > mmax )
                        mmax = dp[i] , p = i;

                }

    }

}

void Write()
{

    out << mmax << '\n';

    int i = p;

    // vector < int > sol;

    while( i != -1 )
    {
       // sol.push_back(v[i]);
        out << v[i] << " ";
        i = poz[i];

    }
    /*
    reverse( sol.begin() , sol.end() );

    for( int i = 0 ; i < sol.size() ; ++i )
        out << sol[i] << " ";

        */
}