Cod sursa(job #2561315)

Utilizator Florinos123Gaina Florin Florinos123 Data 28 februarie 2020 18:44:16
Problema Subsir 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>

using namespace std;

ifstream f ("subsir2.in");
ofstream g ("subsir2.out");

int n, v[5005], best[5005];
int sol[5005], aux[5005], lg, k, maxim;

void read ()
{
  f >> n;
   for (int i=1; i<=n; i++)
      f >> v[i], best[i] = 1;
}

void dinamica ()
{
  for (int i=2; i<=n; i++)
  {
      for (int j=1; j<i; j++)
      {
          if (v[i] > v[j])
          {
              best[i] = max(best[i], best[j]+1);
              maxim = max(maxim, best[i]);
          }
      }
  }
}

void getsubsir (int pozitie)
{
  int i, val = best[pozitie];
  k = 0;
   for (i=pozitie; i>=1; i--)
   {
       if (val == best[i])
       {
           k ++, aux[k] = i;
           val --;
       }
   }
}

void compara ()
{
   int i;
   bool ok = false;
    if (lg == 0)
    {
        for (i=1; i<=k; i++)
        {
            sol[i] = aux[i];
            lg ++;
        }
    }
    else {
        for (i=1; i<=k && !ok; i++)
        {
            if (v[aux[i]] < v[sol[i]])
                ok = true;
        }

        if (ok == true)
        {
            for (i=1; i<=k; i++)
               sol[i] = aux[i];
            lg = k;
        }
    }
}

void solve ()
{
  for (int i=1; i<=n; i++)
  {
      if (best[i] == maxim)
      {
          getsubsir(i);
          compara();
      }
  }
}

void print ()
{
  g << k << '\n';
   for (int i=k; i>=1; i--)
      g << sol[i] << " ";
}

int main()
{
 read();
 dinamica();
 solve();
 print();
    return 0;
}