Cod sursa(job #2562060)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 29 februarie 2020 11:54:57
Problema Subsir 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5005;

int N;
int a[NMAX];
int lis[NMAX];
int pre[NMAX];
bool plpl[NMAX];

void Read()
{
    fin >> N;
    for( int i = 1; i <= N; ++i )
      fin >> a[i];
}

void Do()
{
    for( int i = N; i > 0; --i ) {
       lis[i] = 1;
       pre[i] = i;

       for( int j = i + 1; j <= N; ++j )
         if( a[i] <= a[j] ) {
            plpl[j] = true;
            if( lis[i] < lis[j] + 1 || ( lis[i] == lis[j] + 1 && a[j] < a[ pre[i] ] ) ) {
              lis[i] = lis[j] + 1;
              pre[i] = j;
            }
         }
         else
          if( a[i] <= a[j] ) plpl[j] = true;
    }

    /*for( int i = 1; i <= N; ++i )
      fout << a[i] << ' '; fout << '\n';
    for( int i = 1; i <= N; ++i )
      fout << lis[i] << ' '; fout << '\n';
    for( int i = 1; i <= N; ++i )
      fout << plpl[i] << ' '; fout << '\n';*/


    int lmin = NMAX + 1;
    int p;

    for( int i = 1; i <= N; ++i )
      if( plpl[i] == false ) {
         if( lmin > lis[i] || ( lmin == lis[i] && a[i] < a[p] ) ) {
            lmin = lis[i];
            p = i;
         }
      }

    fout << lmin << '\n';

    while( p != pre[p] ) {
       fout << p << ' ';
       p = pre[p];
    }
    fout << p;
}

int main()
{
    Read();
    Do();

    return 0;
}